oblicz równanie rekurencyjne (reszta z dzielenia)

[mozeto]

\(\displaystyle{ A(n)=\begin{cases} 6 &\text{dla } n=0 \\21 &\text{dla } n=1\\11 &\text{dla } n=2\\3 \cdot A(n-1)+A(n-3)+10 \cdot n+2 &\text{dla } n \ge 3 \end{cases}}\)

Należy udowodnić, że dla tak opisanego równania rekurencyjnego zachodzi zależność: A(n) przystaje do 1 mod(5) dla n większego bądź równego 0.

[octahedron]

Indukcyjnie: mamy \(\displaystyle{ A(0)\equiv A(1)\equiv A(3)\equiv 1\pmod{5}}\). Zakładamy, że \(\displaystyle{ A(n-1)\equiv A(n-2)\equiv A(n-3)\equiv 1\pmod{5}}\) dla \(\displaystyle{ n\ge 3}\), wtedy:
\(\displaystyle{ A(n)=3A(n-1)+A(n-3)+10n+2\equiv 3\cdot 1+1+0+2\equiv 6\equiv 1\pmod{5}}\)