dowód indukcyjny wzoru ogólnego ciągu określonego rekurencyj

[nela196]

Odgadnij wzór ogólny ciągu \(\displaystyle{ (a_n)}\) określonego rekurencyjnie, a następnie go udowodnij.

\(\displaystyle{ \begin{cases} a _{1} = 1\\ a_{2} = -3\\ a_{n+1} = -2a _{n} + 3a _{n - 1} &\mbox{dla } n \ge 2 \end{cases}}\)

wzór ogólny ciągu zgadłam po wypisaniu pierwszych kilku wyrazów i jest to: \(\displaystyle{ a_{n} = (-3) ^{n - 1}}\) ale nie mam pojęcia jak to udowodnić. Poproszę o jak najdokładniejsze wytłumaczenie docenię każdą pomoc
z góry dziekuję

[Benny01]

Najprościej indukcyjnie.

[Rozbitek]

\(\displaystyle{ \left( -3 \right)^{n-1}}\), dla \(\displaystyle{ n = 2}\)

\(\displaystyle{ 9 = 6 + 3}\), zgadza się.

Zatem załóżmy, że \(\displaystyle{ a_{n} = (-3) ^{n - 1}}\)

\(\displaystyle{ a_{n+1} = (-3) ^{n}\\ \\
a_{n} = (-3) ^{n - 1}\\ \\
a_{n-1} = (-3) ^{n - 2}}\)

\(\displaystyle{ (-2)(-3) ^{n - 1} + 3(-3) ^{n - 2} = (-3)^{n-1} (-2-1) = (-3)^{n}}\)

Zgadza się.

teraz sprawdź jak to będzie dla \(\displaystyle{ (n+1)}\).

[Jan Kraszewski]

Zatem załóżmy, że \(\displaystyle{ a_{n} = (-3) ^{n - 1}}\)

\(\displaystyle{ a_{n+1} = (-3) ^{n}\\ \\
a_{n} = (-3) ^{n - 1}\\ \\
a_{n-1} = (-3) ^{n - 2}}\)

\(\displaystyle{ (-2)(-3) ^{n - 1} + 3(-3) ^{n - 2} = (-3)^{n-1} (-2-1) = (-3)^{n}}\)

Zgadza się.

teraz sprawdź jak to będzie dla \(\displaystyle{ (n+1)}\).

Że co?!

Tak to właśnie wygląda, jak się niechlujnie zapisuje dowody indukcyjne.

JK

[Rozbitek]

Droga autorko tematu, z szacunku do Ciebie (i z troski o Twoją umiejętność dowodzenia indukcyjnego) polecam przeanalizować to co napisałem wyżej i spróbować dojść do tego skąd wzięły się poszczególne linijki.

Dla sprawdzenia czy dobrze zrobiłaś i Pana Doktora Jana Kraszewskiego:

Ukryta treść:    

\(\displaystyle{ \begin{cases} a _{1} = 1\\ a_{2} = -3\\ a_{n+1} = -2a _{n} + 3a _{n - 1} &\mbox{dla } n \ge 2 \end{cases}}\)

Pierwszy krok indukcyjny, sprawdźmy czy dla \(\displaystyle{ n = 2}\) zachodzi równość:
\(\displaystyle{ a_{n+1} = -2a _{n} + 3a _{n - 1}}\), gdzie \(\displaystyle{ a_{n} = (-3) ^{n - 1}}\)
\(\displaystyle{ a_3 = -2a_2 + 3a_1}\)
\(\displaystyle{ (-3)^{3-1} = -2a_2 +3a_1}\)

\(\displaystyle{ (-3)^2 = -2 \cdot (-3) + 3 \cdot 1}\)
\(\displaystyle{ 9 = 6 + 3}\), co jest prawdą.

Założenie indukcyjne: \(\displaystyle{ a_n = (-3)^{n-1}}\)

Drugi krok indukcyjny:
Sprawdzam, czy \(\displaystyle{ a_{n+1} = -2a _{n} + 3a _{n - 1}}\) dla \(\displaystyle{ a_n = (-3)^{n-1}}\)
Z założenia indukcyjnego wiemy, że:
1. \(\displaystyle{ a_{n+1} = (-3)^n}\)
2. \(\displaystyle{ a_{n} = (-3)^{n-1}}\)
3. \(\displaystyle{ a_{n-1} = -3^{n-2}}\)

Podstawiając odpowiednie wyrażenia pod sprawdzany wzór:
\(\displaystyle{ (-3)^n = -2 \cdot (-3)^{n-1} + 3 \cdot (-3)^{n-1}}\)
po przemnożeniu dowolnego ze składników przez \(\displaystyle{ (-1)(-1)}\) jego wartość się nie zmieni, więc zapisując w postaci równania równoważnego otrzymuję:
\(\displaystyle{ (-3)^n = -2 \cdot (-3)^{n-1} + (-1)(-1)3 \cdot (-3)^{n-2}}\)

\(\displaystyle{ (-3)^n = -2 \cdot (-3)^{n-1} + (-1)(-3) \cdot (-3)^{n-2}}\)

\(\displaystyle{ (-3)^n = -2 \cdot (-3)^{n-1} + (-1) \cdot (-3)^{n-1}}\)

Wyciągam przed nawias wyrażenie \(\displaystyle{ ((-3)^{n-1})}\)

\(\displaystyle{ (-3)^n = (-3)^{n-1} \left( -2 -1 \right)}\)

\(\displaystyle{ (-3)^n = (-3)^{n}}\)
Co było do okazania. Zatem wzór jest poprawny.

[Jan Kraszewski]

Rozbitku, ode mnie dostałbyś niestety za ten dowód zero punktów.

\(\displaystyle{ \begin{cases} a _{1} = 1\\ a_{2} = -3\\ a_{n+1} = -2a _{n} + 3a _{n - 1} &\mbox{dla } n \ge 2 \end{cases}}\)

Pierwszy krok indukcyjny, sprawdźmy czy dla \(\displaystyle{ n = 2}\) zachodzi równość:
\(\displaystyle{ a_{n+1} = -2a _{n} + 3a _{n - 1}}\), gdzie \(\displaystyle{ a_{n} = (-3) ^{n - 1}}\)
\(\displaystyle{ a_3 = -2a_2 + 3a_1}\)
\(\displaystyle{ (-3)^{3-1} = -2a_2 +3a_1}\)

\(\displaystyle{ (-3)^2 = -2 \cdot (-3) + 3 \cdot 1}\)
\(\displaystyle{ 9 = 6 + 3}\), co jest prawdą.

Źle. Pierwszy krok indukcyjny polega na sprawdzeniu, ze teza zachodzi dla \(\displaystyle{ n=1}\) i \(\displaystyle{ n=2}\). Sprawdzenie dwóch początkowych przypadków jest niezbędne.

A Ty najpierw piszesz trzy zbędne linijki (które tylko zaciemniają sprawę), a potem sprawdzasz tylko jeden warunek, w dodatku nie ten, który powinieneś (bo sprawdzasz, wbrew temu co piszesz, przypadek \(\displaystyle{ n=3}\)).

Założenie indukcyjne: \(\displaystyle{ a_n = (-3)^{n-1}}\)

Nieprawda, to nie jest poprawne założenie indukcyjne. W tym zadaniu nie stosuje się Zasady Indukcji Matematycznej w wersji podstawowej, tylko zmodyfikowanej. Dlatego poprawnie sformułowany początek dowodu kroku indukcyjnego wygląda tak:

Ustalmy dowolną liczbę naturalną \(\displaystyle{ n\ge 2}\) taką, że \(\displaystyle{ a_{n-1} = (-3)^{n-2}}\) i \(\displaystyle{ a_n = (-3)^{n-1}}\).

Natomiast Ty w trakcie dowodu założyłeś sobie tezę. Bardzo wygodne, ale powinieneś wiedzieć, że dowód przez założenie tezy jest niepoprawny.

Drugi krok indukcyjny:
Sprawdzam, czy \(\displaystyle{ a_{n+1} = -2a _{n} + 3a _{n - 1}}\) dla \(\displaystyle{ a_n = (-3)^{n-1}}\)
Z założenia indukcyjnego wiemy, że:
1. \(\displaystyle{ a_{n+1} = (-3)^n}\)
2. \(\displaystyle{ a_{n} = (-3)^{n-1}}\)
3. \(\displaystyle{ a_{n-1} = -3^{n-2}}\)

No to jest tragedia. Dalej już nie komentuję.

Uwaga do neli196 - nie analizuj dowodu Rozbitka, żeby nie nabrać fałszywego przekonania na temat tego, jak powinien wyglądać dowód indukcyjny.

JK

[Rozbitek]

Jan Kraszewski, dowiedziałem się, że popełniłem błędy, jednak nie rozumiem dlaczego to są błędy? Mógłby Pan Doktor wyjaśnić dlaczego:
Muszę założyć, że dla mojego ustalonego \(\displaystyle{ n}\) zachodzą aż dwa warunki: \(\displaystyle{ a_{n-1} = (-3)^{n-2}}\) i \(\displaystyle{ a_n = (-3)^{n-1}}\)? Zwłaszcza że z tego drugiego (jak dla mnie) wynika ten pierwszy (stąd pewnie moje założenie tezy).

Nie rozumiem dlaczego:
\(\displaystyle{ a_n = (-3)^{n-1} \Leftrightarrow a_{n+1} = (-3)^{(n+1)-1}}\) jest błędne?
Bo własnie z tego wynikają moje trzy "tragiczne" punkty.

[Jan Kraszewski]

Jan Kraszewski, dowiedziałem się, że popełniłem błędy, jednak nie rozumiem dlaczego to są błędy?

Twój podstawowy problem polega na tym, że nie rozumiesz, na czym polega dowód indukcyjny. Akurat ten dowód indukcyjny jest ciut bardziej skomplikowany, ale obawiam się, że nawet typowego dowodu indukcyjnego nie potrafisz przeprowadzić poprawnie.

Zasada Indukcji Matematycznej (ZIM) stanowi, że

Jeśli \(\displaystyle{ \varphi(n)}\) jest funkcją zdaniowa zmiennej naturalnej taką, że

\(\displaystyle{ 1)\ \varphi(0)}\)
i
\(\displaystyle{ 2)\ (\forall n\in\NN)(\varphi(n) \Rightarrow \varphi(n+1))}\)

to wtedy \(\displaystyle{ \red(\forall n\in\NN)\varphi(n)}\).

Zastosowanie ZIM polega zatem na sprawdzeniu założeń ZIM, czyli \(\displaystyle{ 1)}\) i \(\displaystyle{ 2)}\), a następnie na powołaniu się na ZIM, by otrzymać tezę.

Musisz mieć świadomość, że sprawdzenie \(\displaystyle{ 1)}\) (kroku bazowego) i \(\displaystyle{ 2)}\) (kroku indukcyjnego) to są dwa osobne rozumowania, których nie należy mylić z zastosowaniem ZIM (czyli wywnioskowaniem tezy).

W szczególności sprawdzanie \(\displaystyle{ 2)}\) polega na udowodnieniu osobnego twierdzenia. W tym celu ustalasz dowolne \(\displaystyle{ n\in\NN}\) takie, że zachodzi \(\displaystyle{ \varphi(n)}\) i dla tego ustalonego \(\displaystyle{ n}\) pokazujesz, że zachodzi \(\displaystyle{ \varphi(n+1)}\). Pamiętaj, \(\displaystyle{ n}\) ma być ustalone, pod żadnym pozorem nie wolno w kroku indukcyjnym "zakładać", że \(\displaystyle{ \red(\forall n\in\NN)\varphi(n)}\) (a mniej więcej to właśnie zrobiłeś).

To jest podstawowa wersja ZIM, ale jest dużo innych wersji ZIM (równoważnych), które stosuje się w konkretnych sytuacjach. W interesującym nas zadaniu potrzebujemy takiej zasady indukcji:

\(\displaystyle{ \varphi(1)\land \varphi(2)\land(\forall n\ge 2)(\varphi(n-1)\land\varphi(n) \Rightarrow \varphi(n+1)) \Longrightarrow \red(\forall n\ge 1)\varphi(n).}\)

Jak nie sprawdzisz na początku obu warunków \(\displaystyle{ \varphi(1), \varphi(2)}\), to nie masz szans dostać, że prawdziwe jest \(\displaystyle{ \varphi(3)}\) - przemyśl to. Poza tym w kroku indukcyjnym znowu bierzesz dowolne ustalone \(\displaystyle{ n\ge 2}\), dla którego prawdziwe są \(\displaystyle{ \varphi(n-1)}\) \(\displaystyle{ \varphi(n)}\) i przy tych założeniach, dla tego ustalonego \(\displaystyle{ n}\), pokazujesz, że zachodzi \(\displaystyle{ \varphi(n+1)}\).

Mógłby Pan Doktor wyjaśnić dlaczego:
Muszę założyć, że dla mojego ustalonego \(\displaystyle{ n}\) zachodzą aż dwa warunki: \(\displaystyle{ a_{n-1} = (-3)^{n-2}}\) i \(\displaystyle{ a_n = (-3)^{n-1}}\)? Zwłaszcza że z tego drugiego (jak dla mnie) wynika ten pierwszy (stąd pewnie moje założenie tezy).

Z tego drugiego w żaden sposób nie wynika pierwszy, bo \(\displaystyle{ n}\) jest ustalone, więc drugi warunek mówi coś o \(\displaystyle{ a_n}\), ale nie mówi nic o \(\displaystyle{ a_{n-1}}\)

Nie rozumiem dlaczego:
\(\displaystyle{ a_n = (-3)^{n-1} \Leftrightarrow a_{n+1} = (-3)^{(n+1)-1}}\) jest błędne?

Jak wyżej: \(\displaystyle{ n}\) jest ustalone, nie masz prawa nim manipulować, nie masz żadnego "ogólnego" wzoru.

Ale tak naprawdę najważniejsze jest zrozumienie, na czym w ogóle polegają dowody indukcyjne, jaki jest sens indukcji, bo w przeciwnym razie jesteś skazany na dość beznadziejne manipulowanie znaczkami. No ale mnie wytłumaczenie tego zajmuje zazwyczaj godzinę wykładu, więc nie oczekuj, że będę tę godzinę "przeklepywał" na forum...

JK

[Rozbitek]

Jaka jest idea założenia indukcyjnego:
Dla ustalonego \(\displaystyle{ n \ge 2}\):
\(\displaystyle{ a_{n-1} = (-3)^{n-2} \wedge a_n = (-3)^{n-1}}\)?

Bo utknąłem przy drugim kroku indukcyjnym, co właściwie mam udowodnić? Bo rozumiem, że nie mogę sobie założyć, że \(\displaystyle{ a_{n+1} = (-3)^n}\)?
Mam do tego dojść?

Czyli: \(\displaystyle{ -2 \cdot (-3)^{n-1} + 3 \cdot (-3)^{n-2} = (...) = (-3)^{n}}\)

Oczywiście po sprawdzeniu czy dla \(\displaystyle{ n = 1}\) i \(\displaystyle{ n = 2}\), wzór jest prawdziwy...

[Jan Kraszewski]

Bo utknąłem przy drugim kroku indukcyjnym, co właściwie mam udowodnić? Bo rozumiem, że nie mogę sobie założyć, że \(\displaystyle{ a_{n+1} = (-3)^n}\)?
Mam do tego dojść?

Masz udowodnić, że spełnione jest założenie ZIM:

\(\displaystyle{ (\forall n\ge 2)(\varphi(n-1)\land\varphi(n) \Rightarrow \varphi(n+1))}\)

Rozumiesz to? Rozumiesz jak to udowodnić?

JK

[Rozbitek]

Obawiam się, że nie.
Nie rozumiem w ogóle czemu mam sprawdzać czy założenie jest spełnione... Przecież założenie to założenie, ono jest spełnione z natury rzeczy (?)

[Jan Kraszewski]

Nie rozumiem w ogóle czemu mam sprawdzać czy założenie jest spełnione... Przecież założenie to założenie, ono jest spełnione z natury rzeczy (?)

Uch...

Znasz twierdzenie mówiące, że jeśli ciąg liczb rzeczywistych jest monotoniczny i ograniczony, to jest zbieżny? Wyobraź sobie, że za pomocą tego twierdzenia chcesz udowodnić, że ciąg \(\displaystyle{ a_n=\frac{n-1}{n}}\) jest zbieżny. Jak to robisz? Pokazujesz, że ten ciąg spełnia założenia ww. twierdzenia, czyli że jest monotoniczny i ograniczony, a potem powołujesz się na twierdzenie i mówisz, że na jego mocy ów ciąg jest zbieżny.

Z indukcją jest tak samo: jeśli za pomocą ZIM chcesz pokazać, że jakaś formuła \(\displaystyle{ \varphi(n)}\) zachodzi dla każdej liczby naturalnej, to musisz udowodnić, że formuła ta spełnia założenia ZIM, a potem powołać się na ZIM.

JK

[Rozbitek]

Czyli:
z \(\displaystyle{ a_{n-1} = (-3)^{n-2} \wedge a_{n} = (-3)^{n-1}}\) ma wynikać \(\displaystyle{ a_{n}=(-3)^n}\)?

\(\displaystyle{ \left( -2 \right) \left( -3 \right)^{n-1} + 3\left( -3\right)^{n-2} = \left( -3\right)^{n-2} \left( 6 + 3\right) = \left( -3\right)^{n-2} \cdot (-3)^2 = (-3)^{n}}\)

[Jan Kraszewski]

Czyli:
z \(\displaystyle{ a_{n-1} = (-3)^{n-2} \wedge a_{n} = (-3)^{n-1}}\) ma wynikać \(\displaystyle{ a_{n}=(-3)^n}\)?

Nie. Dla dowolnie ustalonego \(\displaystyle{ \red n}\), z \(\displaystyle{ a_{n-1} = (-3)^{n-2} \wedge a_{n} = (-3)^{n-1}}\) ma wynikać \(\displaystyle{ a_{n\red +1\black}=(-3)^n}\).

Nie tylko rachunki są ważne, komentarz też.

\(\displaystyle{ \left( -2 \right) \left( -3 \right)^{n-1} + 3\left( -3\right)^{n-2} = \left( -3\right)^{n-2} \left( 6 + 3\right) = \left( -3\right)^{n-2} \cdot (-3)^2 = (-3)^{n}}\)

No liczyć umiesz, ale opisać tego już nie. Powtórzę: same rachunki to za mało. A Ty napisałeś linijkę jakichś rachunków z niewyrażonym werbalnie komentarzem "sami się domyślcie, co liczę"...

JK

[Rozbitek]

W równaniu \(\displaystyle{ a_{n+1} = -2a _{n} + 3a _{n - 1}}\) pod prawą stronę podstawiłem założone wartości i doszedłem do \(\displaystyle{ (-3)^n}\)

W pierwszym przejściu "wyciągnąłem przed nawias" wyrażenie \(\displaystyle{ (-3)^{n-2}}\), w drugim zapisałem \(\displaystyle{ 9}\) w postaci \(\displaystyle{ (-3)^2}\), a w ostatnim skorzystałem z własności mnożenia ułamków o tej samej podstawie.