Podać jawny wzór na \(a_{n}\) oraz udowodnić indukcyjnie jego poprawność:
\(a_{n}=3a_{n-1}+a_{n-2}\)
\(a_{0}=1\)
\(a_{1}=1\)
Nie mam pojęcia jak się za to zabrać i proszę o pomoc.
Z góry dziękuję i pozdrawiam.
jawny wzór oraz indukcyjne udowodnienie jego poprawności
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Skorzystamy z metody funkcji tworzących.
Funkcja tworząca dla tego ciągu to \(f(x)=\sum_{n=0}^\infty a_nx^n\).
Podstawiamy \(a_n=3a_{n-1}+a_{n-2}\)
\(f(x)=a_0x^0+a_1x^1+\sum_{n=2}^\infty a_nx^n=1+x+\sum_{n=2}^\infty(3a_{n-1}+a_{n-2})x^n=1+x+\sum_{n=2}^\infty3a_{n-1}x^n+\sum_{n=2}^\infty a_{n-2}x^n=
=1+x+3x\sum_{n=2}^\infty a_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty a_{n-2}x^{n-2}=1+x+3x(f(x)-a_0x^0)+x^2f(x)\)
Wyznaczamy z tego f(x)
\(f(x)=\frac{1-2x}{1-3x-x^2}\)
Rozwiązujemy równanie \(\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{1-2x}{1-3x-x^2}\) (wyznaczamy współczynniki A,B,a,b). Otrzymujemy
\(a=\frac{3+\sqrt{13}}{2},\quad b=\frac{3-\sqrt{13}}{2},\quad A=\frac{a-2}{a-b},\quad B=\frac{2-b}{a-b}\)
Zatem
\(f(x)=A\frac{1}{1-ax}+B\frac{1}{1-bx}\)
Na ułamki przy współczynnikach A,B możemy spojrzeć jak na sumy szeregów geometrycznych
\(f(x)=A\sum_{n=0}^\infty(ax)^n+B\sum_{n=0}^\infty(bx)^n=\sum_{n=0}^\infty x^n\left(\frac{a^{n+1}-2a^n+2b^n-b^{n+1}}{a-b}\right)=\sum_{n=0}^\infty x^na_n=\)
Stąd
\(a_n=\frac{a^{n+1}-2a^n+2b^n-b^{n+1}}{a-b}=\frac{a^n(a-2)+b^n(2-b)}{a-b}=\left(\frac{3+\sqrt{13}}{2}\right)^n\cdot\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^n\cdot\frac{1+\sqrt{13}}{2\sqrt{13}}\)
Funkcja tworząca dla tego ciągu to \(f(x)=\sum_{n=0}^\infty a_nx^n\).
Podstawiamy \(a_n=3a_{n-1}+a_{n-2}\)
\(f(x)=a_0x^0+a_1x^1+\sum_{n=2}^\infty a_nx^n=1+x+\sum_{n=2}^\infty(3a_{n-1}+a_{n-2})x^n=1+x+\sum_{n=2}^\infty3a_{n-1}x^n+\sum_{n=2}^\infty a_{n-2}x^n=
=1+x+3x\sum_{n=2}^\infty a_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty a_{n-2}x^{n-2}=1+x+3x(f(x)-a_0x^0)+x^2f(x)\)
Wyznaczamy z tego f(x)
\(f(x)=\frac{1-2x}{1-3x-x^2}\)
Rozwiązujemy równanie \(\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{1-2x}{1-3x-x^2}\) (wyznaczamy współczynniki A,B,a,b). Otrzymujemy
\(a=\frac{3+\sqrt{13}}{2},\quad b=\frac{3-\sqrt{13}}{2},\quad A=\frac{a-2}{a-b},\quad B=\frac{2-b}{a-b}\)
Zatem
\(f(x)=A\frac{1}{1-ax}+B\frac{1}{1-bx}\)
Na ułamki przy współczynnikach A,B możemy spojrzeć jak na sumy szeregów geometrycznych
\(f(x)=A\sum_{n=0}^\infty(ax)^n+B\sum_{n=0}^\infty(bx)^n=\sum_{n=0}^\infty x^n\left(\frac{a^{n+1}-2a^n+2b^n-b^{n+1}}{a-b}\right)=\sum_{n=0}^\infty x^na_n=\)
Stąd
\(a_n=\frac{a^{n+1}-2a^n+2b^n-b^{n+1}}{a-b}=\frac{a^n(a-2)+b^n(2-b)}{a-b}=\left(\frac{3+\sqrt{13}}{2}\right)^n\cdot\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^n\cdot\frac{1+\sqrt{13}}{2\sqrt{13}}\)
Wkońcu znlazłem chwilę żeby dokończyć. Dowód poprawności wzoru
Pokazujemy, że wzór jest prawdziwy dla k=0
\(\left(\frac{3+\sqrt{13}}{2}\right)^0\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^0\frac{\sqrt{13}+1}{2\sqrt{13}}=1=a_0\)
Zakładamy, że wzór jest prawdziwy dla \(k\leq n\) pokażemy, że wzór jest również prawdziwy dla k=n+1.
\(a_{n+1}=3a_n+a_{n-1}=
=3\left(\frac{3+\sqrt{13}}{2}\right)^n\frac{\sqrt{13}-1}{2\sqrt{13}}+3\left(\frac{3-\sqrt{13}}{2}\right)^n\frac{\sqrt{13}+1}{2\sqrt{13}}+\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\frac{\sqrt{13}+1}{2\sqrt{13}}=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(3\frac{3-\sqrt{13}}{2}+1\right)+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(3\frac{3+\sqrt{13}}{2}+1\right)=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(\frac{22-6\sqrt{13}}{4}\right)+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(\frac{22+6\sqrt{13}}{4}\right)=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(\frac{3-\sqrt{13}}{2}\right)^2+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(\frac{3+\sqrt{13}}{2}\right)^2=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}\)
Pokazujemy, że wzór jest prawdziwy dla k=0
\(\left(\frac{3+\sqrt{13}}{2}\right)^0\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^0\frac{\sqrt{13}+1}{2\sqrt{13}}=1=a_0\)
Zakładamy, że wzór jest prawdziwy dla \(k\leq n\) pokażemy, że wzór jest również prawdziwy dla k=n+1.
\(a_{n+1}=3a_n+a_{n-1}=
=3\left(\frac{3+\sqrt{13}}{2}\right)^n\frac{\sqrt{13}-1}{2\sqrt{13}}+3\left(\frac{3-\sqrt{13}}{2}\right)^n\frac{\sqrt{13}+1}{2\sqrt{13}}+\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\frac{\sqrt{13}-1}{2\sqrt{13}}+\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\frac{\sqrt{13}+1}{2\sqrt{13}}=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(3\frac{3-\sqrt{13}}{2}+1\right)+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(3\frac{3+\sqrt{13}}{2}+1\right)=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(\frac{22-6\sqrt{13}}{4}\right)+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(\frac{22+6\sqrt{13}}{4}\right)=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n-1}\left(\frac{3-\sqrt{13}}{2}\right)^2+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n-1}\left(\frac{3+\sqrt{13}}{2}\right)^2=
=\frac{1+\sqrt{13}}{2\sqrt{13}}\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}+\frac{\sqrt{13}-1}{2\sqrt{13}}\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}\)