Rozwiązanie równania rekurencyjnego

[Dyzioo]

Cześć!

Trudzę się obecnie z takim zadaniem:

Dany jest algorytm:

Kod: Zaznacz cały

a(n)
if n ==0 then return 6
if n == 1 then return 21
if n == 2 then return 11
if n > 2 then return 3 * a(n-1) + a(n-3) + 10*n + 2

Pokaż że dla całkowitego \(\displaystyle{ n \ge 0}\) zachodzi \(\displaystyle{ a(n) = 1 \mod 5}\)

Jakieś wskazówki jak do tego podejść? Próbować indukcji czy od razu startować z funkcjami tworzącymi?

[Premislav]

lol, oto zdarzy się niemożliwe i wypowiem się w dziale Informatyka.

Ja bym przeprowadził dowód indukcyjny. Funkcjami tworzącymi też można (żeby znaleźć wzór ogólny na \(\displaystyle{ a(n)}\)), ale to chyba więcej obliczeń.
\(\displaystyle{ 1^{\circ}}\) Dla \(\displaystyle{ n=0, n=1, n=2}\) bezpośrednio sprawdzamy, że jest to prawda (tj. \(\displaystyle{ a(0)=6\equiv 1\pmod{5}}\) itd.).
\(\displaystyle{ 2^{\circ}}\) Jeżeli mamy \(\displaystyle{ a(n-3) \equiv 1\pmod{5}, a(n-2)\equiv 1\pmod{5}, a(n-1)\equiv 1 \pmod{5}}\), to
\(\displaystyle{ a(n)=3a(n-1)+a(n-3)+10n+2 \equiv 3+1+2\pmod{5}}\),
a to kończy drugi krok indukcyjny, bo \(\displaystyle{ 3+1+2=6\equiv 1\pmod{5}}\).