Udowodnienie twierdzenia przez indukcję (rekurencja)

[765487]

Proszę o pomoc z tym zadaniem. (Wiem, jak to zrobić za pomocą wielomianu charakterystycznego i za pomocą macierzy, ale potrzebuję zrobić to za pomocą indukcji i nie wiem jak)
Udowodnić, że jeżeli:
\(\displaystyle{ (a_0=6 \wedge a_1=11 \wedge a_n=3a _{n-1}-2a_{n-2}) \Rightarrow a_{n}=5\cdot2^{n}+1}\)

[Jan Kraszewski]

Prosto.

W kroku bazowym dla \(\displaystyle{ n=0}\) i \(\displaystyle{ n=1}\) masz \(\displaystyle{ a_0=5\cdot 2^0+1=5+1=6}\) i \(\displaystyle{ a_1=5\cdot 2^1+1=5\cdot 2+1=11}\), czyli zgadza się.

Teraz ustalasz dowolne \(\displaystyle{ n\in\NN}\) takie, że teza zachodzi dla \(\displaystyle{ n}\) i \(\displaystyle{ n+1,}\) czyli \(\displaystyle{ a_n=5\cdot 2^n+1}\) i \(\displaystyle{ a_{n+1}=5\cdot 2^{n+1}+1}\) i pokazujesz, że wówczas zachodzi także dla \(\displaystyle{ n+2}\) (czyli \(\displaystyle{ a_{n+2}=5\cdot 2^{n+2}+1}\)).

Istotnie, korzystając najpierw z definicji ciągu, a potem z założenia indukcyjnego mamy

\(\displaystyle{ a_{n+2}=3a_{n+1}−2a_n=3\left( 5\cdot 2^{n+1}+1\right)-2\left(5\cdot 2^n+1 \right)= 15\cdot 2^{n+1}+3-10\cdot 2^n-2= 30\cdot 2^n-10\cdot 2^n+1=20\cdot 2^n+1 =5\cdot 2^{n+2}+1.}\)

Powołanie się na Zasadę Indukcji Matematycznej (a w zasadzie na pewną jej mutację) kończy dowód.

JK

[765487]

Rzeczywiście banalne, zapomniałem, że mogę podstawić założenie indukcyjne pod definicję ciągu, dzięki.