773 zadań 576 rozwiązań 530 użytkowników
zaloguj się

jawny wzór na Sn oraz udowodnić indukcyjnie jego poprawność

a_{n}=-2a_{n-1}+2a_{n-2}\\ \\ a_{0}=1\\ a_{1}=2

To nie jest, żadne "zadanie z gwiazdką".
-dzakub

A masz jakiś przykład takiego zadania, w którym pierwiastki są urojone? Może wrzucisz?
-modalmen

Pewnie, że mam:
http://www.majca.pl/zadanie/wyprowadzic-wzor-jawny-na-an,351
-dzakub

1 rozwiązania

Podana rekurencja jest rekurencją liniową.
Jawny wzór dla tego typu rekurencji wylicza się za pomocą równania charakterystycznego rekurencji.
Całe twierdzenie wraz z dowodem można znaleźć np. w książce Normana Biggsa "Discrete Mathematics".
Mówi on tyle, że dla rekurencji liniowej postaci:
a_{n+2} +u_{1}a_{n+1}+u_{2}a_{n}=0 \\ a_{0}=c_{0} \\ a_{1}=c_{1}

równanie charakterystyczne ma postać:
t^{2}+u_{1}t+u_{2}=0

I jeśli \alpha oraz \beta są pierwiastkami, równania charakterystycznego,
to wzór jawny na n-ty wyraz rekurencji ma postać:
a_{n}=A\alpha ^{n}+B\beta ^{n} dla \alpha \neq \beta
a_{n}=(Cn+D)\alpha ^{n} dla \alpha =\beta

A, B, C, D są stałymi zdeterminowanymi przez c_{0} oraz c_{1}.
Powyższe twierdzenie jest prawdziwe dla n\geq 0.

Rozwiązanie zadania.
1) Wyznaczenie wzoru jawnego na a_{n}:
Dla powyższej rekurencji, równanie charakterystyczne ma postać:
t^{2}+2t-2=0

Wyliczmy pierwiastki:
\Delta =2^{2}+8=12\\ \alpha =-1-\sqrt{3}\\ \beta =-1+\sqrt{3}

Zatem:
a_{n}=A(-1-\sqrt{3})^{n}+B(-1+\sqrt{3})^{n} (1)

Wyznaczamy A, B rozwiązując następujący układ równań:
\left\{ 1=A+B\\ 2=A(-1-\sqrt{3})+B(-1+\sqrt{3}) \right.

Obliczenia nie są zbyt twórcze więc, je pomijam. Otrzymujemy:
A=\frac{1}{2}(1+\sqrt{3})\\ B=\frac{1}{2}(1-\sqrt{3}) (2)

Wstawiając (2) do (1) otrzymujemy wzór jawny na a_{n}:
a_{n}=\frac{1}{2}\left[ (1-\sqrt{3})(-1-\sqrt{3})^{n}+(1+\sqrt{3})(-1+\sqrt{3})^{n} \right] (3)

2) Dowód poprawności wzoru (3) przy użyciu zasady indukcji matematycznej.
W pierwszym kroku sprawdzamy poprawność wzoru dla n=0 i n=1,
jednak ponieważ wartości stałych A, B zostały tak wyznaczone,
by wzór był prawdziwy dla n=0 oraz n=1, możemy uznać, ze zostało to już zrobione.

Przechodzimy do drugiego kroku zasady indukcji matematycznej. Dowodzimy prawdziwość wzoru w kroku następnym z prawdziwości wzoru w kroku poprzednim.
Z rekurencyjnej postaci wzoru na a_{n} oraz z (3) mamy:
a_{n}=-(1-\sqrt{3})(-1-\sqrt{3})^{n-1}-(1+\sqrt{3})(-1+\sqrt{3})^{n-1}+(1-\sqrt{3})(-1-\sqrt{3})^{n-2}+(1+\sqrt{3})(-1+\sqrt{3})^{n-2}\\ =(-1-\sqrt{3})^{n-2}\left[ (1-\sqrt{3})-(1-\sqrt{3})(-1-\sqrt{3}) \right]+(-1+\sqrt{3})^{n-2}\left[ (1+\sqrt{3})-(1+\sqrt{3})(-1+\sqrt{3}) \right]\\ =(1-\sqrt{3})(-1-\sqrt{3})^{n-2}(2+\sqrt{3})+(1+\sqrt{3})(-1+\sqrt{3})^{n-2}(2-\sqrt{3})

Można zauważyć, że:
\frac{1}{2}(-1-\sqrt{3})^{2}=2+\sqrt{3}\\ \\ \frac{1}{2}(-1+\sqrt{3})^{2}=2-\sqrt{3}

Wykorzystując to, co spostrzegliśmy i wcześniejsze obliczenia otrzymujemy:
a_{n}=\frac{1}{2}\left[ (1-\sqrt{3})(-1-\sqrt{3})^{n}+(1+\sqrt{3})(-1+\sqrt{3})^{n} \right]
czyli nasz wcześniej otrzymany wzór. Zatem z prawdziwości wzoru w krokach poprzednich, wynika prawdziwość wzoru w kroku następnym. Zatem przy użyciu zasady indukcji matematycznej dowiedliśmy poprawności wyliczonego wzoru.

Uwaga:
Tego typu zadania robi się na tzw. "jedno kopyto". Prawdziwa jazda zaczyna się kiedy pierwiastki równania charakterystycznego są urojone. Ale wtedy też można sobie poradzić.

Dodaj nowe zadanie

Przypisane tagi