rekurencja i indukcja porządkowa

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Paragon16
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 23 paź 2011, o 22:46
Płeć: Mężczyzna
Lokalizacja: Warszawa

rekurencja i indukcja porządkowa

Post autor: Paragon16 »

Witam
Mam problem z rozwiązaniem tego zadania :
Dany jest ciąg zdefiniowany rekurencyjnie.
\(\displaystyle{ a_{0}=1, a_{1}=3, a_{2}=5, a_{n}= 3{a _{n-1} } + 2{a _{n-3} }}\) dla \(\displaystyle{ n\ge 3}\)
Udowodnij za pomocą indukcji porządkowej, że \(\displaystyle{ a_{n} < 2^{n+1}}\) dla \(\displaystyle{ n\ge 1}\)
Próbowałem zacząć od napisania równanie charakterystycznego ale już tam pojawia się problem.
Ostatnio zmieniony 18 gru 2012, o 08:51 przez , łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

rekurencja i indukcja porządkowa

Post autor: »

\(\displaystyle{ a_{0}=1, a_{1}=3, a_{2}=5, a_{n}= 3{a _{n-1} } + 2{a _{n-3} }}\) dla \(\displaystyle{ n\ge 3}\)
\(\displaystyle{ a_{n} < 2^{n+1}}\) dla \(\displaystyle{ n\ge 1}\)
W tej wersji to nieprawda, bo na przykład \(\displaystyle{ a_3=17>2^{4}}\)

Zgaduję zatem, że źle przepisałeś przykład i chodzi o rekurencję:
\(\displaystyle{ a_{n}= 3{a _{n-2} } + 2{a _{n-3} }}\)

Wówczas oczywiście dla \(\displaystyle{ n=1}\) twierdzenie jest prawdziwe.
Ustalmy więc dowolne \(\displaystyle{ n}\) i załóżmy, że twierdzenie jest prawdziwe dla wszystkich liczb mniejszych od \(\displaystyle{ n}\), w szczególności \(\displaystyle{ a_{n-2}<2^{n-1}}\) i \(\displaystyle{ a_{n-3}<2^{n-2}}\). Wówczas:
\(\displaystyle{ a_n = 3{a _{n-2} } + 2{a _{n-3} }<3\cdot 2^{n-1} + 2\cdot 2^{n-2} =3\cdot 2^{n-1} + 2^{n-1} = 4\cdot 2^{n-1}=2^{n+1}}\)
czyli twierdzenie jest prawdziwe także dla \(\displaystyle{ n}\), co kończy dowód.

Q.
ODPOWIEDZ