Matematyka dla liceum/Ciągi liczbowe/Rekurencja i indukcja matematyczna: Różnice pomiędzy wersjami

Usunięta treść Dodana treść
m poprawa nawigacji
Piotr (dyskusja | edycje)
mNie podano opisu zmian
Linia 4:
poprzart=Ciągi liczbowe:Inne przykłady ciągów|
nast=Granica ciągu liczbowego|
nastart=Ciągi liczbowe:Granica ciągu liczbowego}} + (k+1) </math>
 
{{WEdycji}}
</noinclude>
 
== Rekurencja ==
Ze wzoramy opisywanymi rekurencyjnie spotkaliśmy się już wcześniej. Na przykład, wiemy, że dla dowolnego ciągu arytmetycznego o różnicy ''r=5'' zachodzi:
: <math> a_{n+1} = a_n + 5 </math>,
czyli każdy wyraz ciągu jest większy o ''5'' od poprzedniego. Podobnie wiemy, że w ciągu geometrycznym o ilorazie ''q=7'' zachodzi:
: <math> a_{n+1} = a_n \cdot 7 </math>.
Podobnie, gdy powiemy, że w kolejce pierwszy przy kasie stoi Józek, za Józkiem stoi Maryśka, za Maryśką stoi Krzysiek, a za Krzyśkiem Kaśka, także się posłużymy '''rekurencją''', nazywaną także '''rekursją'''.
 
Ciężko podać konkretną definicję rekurencji. Jest to pewien sposób określania pewnych zależności na podstawie innych. Innym przykładem rekurencji jest czynność sprzątania zabawek:
: chwyć zabawkę, schowaj ją do szafy i sprzątaj dalej... (aż nie posprzątasz)
czy też liczenia od 100 do 0:
: mamy 100. odejmujemy 1 i mamy 99 i liczymy dalej, tym razem od 99 do 0.
 
Zobaczmy kilka przykładów ciągów określonych rekurencyjnie:
* ciąg artmetyczny <math> (a_n) </math> określony wzorem:
*: <math> a_n = \left\{\begin{matrix}
3 & \mbox{ dla } n = 1 \\
a_{n-1} + 2 & \mbox{ dla } n > 1
\end{matrix}\right.</math>
W tym przypadku widzimy na przykład, że:
 
<math>
a_{5} = a_4 + 2 = (a_3 + 2) + 2 = ((a_2 + 2) + 2) + 2 = (((a_1 + 2) + 2) + 2) + 2 = (((3 + 2) + 2) + 2) + 2 = 11 </math>. Wiedząc, że <math> a_1 = 3 </math> i <math> r = 2 </math> i korzystając, ze wzoru ogólnego na n-ty wyraz ciągu arytmetycznego możemy wynik <math> a_5 = 3 + (5-1) \cdot 2 = 11 </math>, dochodzimy, do takiego samego wyniku.
 
* ciąg geometryczny <math> (b_n) </math>, gdzie:
*: <math> a_1 = 10 </math>
*: <math> a_{n+1} = a_n \cdot 6 \mbox{ dla } n \geq 1</math>
W tym przypadku widzimy, że n-ty wyraz jest 6 razy większy od poprzedniego. Ze wzoru rekurencyjnego możemy wyliczyć, że:
: <math> a_3 = a_2 \cdot 6 = (a_1 \cdot 6) \cdot 6 = (10 \cdot 6) \cdot 6 = 360 </math>.
 
W poprzednim rozdziale widzieliśmy nieco skomplikowany ciąg nazywany, który jest zdefniowany wzorem:
*: <math> F_1 = 1 </math>
*: <math> F_2 = 1 </math>
*: <math> F_n = F_{n-1} + F_{n-2} \mbox{ dla } n > 2</math>.
Policzmy teraz <math> F_5 </math>:
: <math> F_5 = F_4 + F_3 = (F_3 + F_2) + (F_1 + F_2) = ((F_2 + F_1) + 1) + (1 + 1) = ((1 + 1) + 1) + (1 + 1) = 5 </math>.
 
Powinniśmy już pamiętać, że ciąg zdefiniowany wzorem:
: <math> a_1 = x </math>
: <math> a_{n+1} = a_{n} + r \mbox{ dla } n \geq 1 </math>,
posiada postać zwartą, czyli bez rekurencji, w postaci:
: <math> a_n = a_1 + (n-1) \cdot r \mbox{ dla } n \geq 1 </math>. (Jak pamiętamy, jest to ciąg arytmetyczny.)
 
Natomiast postać zwarta ciągu geometrycznego zdefiniowanego wzorem:
: <math> a_1 = x </math>
: <math> a_{n+1} = a_n \cdot q \mbox{ dla } n \geq 1 </math>
będzie postaci:
: <math> a_n = a_1 \cdot q^{n-1} \mbox{ dla } n \geq 1</math>,
a co już zresztą wiemy.
 
== Indukcja matematyczna ==
Indukcja matematyczna to jeden ze sposobów dowodzenia pewnych twierdzeń. Pokazujemy, że dane twierdzenie jest prawdziwe dla pewnej wartości początkowej (np. dla 10), a następnie uzasadniamy, że twierdzenie jest prawdziwe dla większych wartości (np. dla 11, 12, 13 itd.), korzystając z prawdziwości twierdzenie dla mniejszych wartości (czyli np. uzasadniamy, że dla 11 twierdzenie jest prawdziwe, wykorzystując do tego 10). Teoretyczne podstawy już znamy (przynajmniej teoretycznie), to przejdźmy do praktyki.
 
Udowodnijmy za pomocą indukcji, że jeśli dodamy sto jedynek, to otrzymamy liczbę sto.
Zauważmy, że dodając k jedynek (np. <math>k=30</math>), najpierw dodajemy k-1 jedynek (np. <math>k-1=30-1=29</math>), a potem jeszcze jedną, czyli:
: <math> S_1 = 1 </math>
: <math> S_k = S_{k-1} + 1 </math> np. <math> S_{30} = S_{29} + 1 </math>
 
Z tego co pisze wyżej o indukcji, wynika, że najpierw musimy uzasadnić, że twierdzenie jest prawdziwe dla pewnej początkowej wartości, więc weźmy jedynkę:
: <math> S_1 = 1 </math>. Dodając jedną jedynkę otrzymujemy po prostu ''1'', czyli wszystko OK.
Możemy jeszcze sprawdzić dla dwójki:
: <math> S_2 = 1 + 1 = 2 </math> i znowu się zgadza.
Czyli pewnie wzór będzie się zgadzał dla wszystkich liczb <math> i \in \{1, 2, ..., 10\} </math>, czy też nawet dla <math> i \in \{1, 2, ..., k\} </math> (dla pewnego określonego k np. równego 50), co zapiszemy:
: <math> S_i = i \mbox{ dla } i \in \{1, 2, ..., k\} </math> (nasze założenie)
Czy wzór będzie się zgadzał dla <math> i = k + 1 </math>? Sprawdźmy:
: <math> S_i = S_{k+1} = {\color[rgb]{0.0,0.0,0.6}S_k} + 1 </math> (skorzystaliśmy ze wzoru <math> S_{i} = S_{i-1} + 1 </math>).
Wiemy z założenia przedstawionego ciut wyżej, że <math> {\color[rgb]{0.0,0.0,0.6}S_k = k} </math>, zatem:
: <math> S_{k+1} = {\color[rgb]{0.0,0.0,0.6} k} + 1 = k + 1 </math>.
Czyli do zbioru dla którego nasze twierdzenie jest prawdziwe <math> \{1, 2, ..., k\} </math> możemy wepchać następną liczbę, czyli ''k+1''. I tak dokładając ''2'', ''3'', ''4'' i następne liczby dochodzimy aż do '''100'''. Zatem udowodniliśmy to twierdzenie. Już jesteśmy pewni, że jeśli dodamy sto jedynek otrzymamy liczbę sto!
 
Podsumujmy w skrócie, co zrobiliśmy. Otóż wykonaliśmy poniższe kroki:
# Pokazaliśmy, że jest prawdziwe dla 1.
# Założyliśmy, że w takim razie będzie prawdziwe dla 1, 2, 3, ..., k.
# Pokazaliśmy, że skoro jest prawdziwe od 1 do k, więc musi być także prawdziwe dla k + 1.
# Stwierdziliśmy, że musi być prawdziwe dla wszystkich ''n'', czyli także 100.
 
 
 
Teraz udowodnijmy, że <math> 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} </math>.
: Najpierw musimy sprawdzić '''dla n=1''':
:: <math> L = 1 </math>, ponieważ dodaliśmy tylko jedną liczbę -- 1.
:: <math> P = \frac{1\cdot(1+1)}{2} = 1 </math>.
:: Zgadza się, <math> L = P </math>.
 
Czyli teraz możemy stworzyć odpowiednie założenie.
: '''Założenie indukcyjne dla n = k:'''
:: <math> {\color[rgb]{0.0,0.0,0.6}1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}} </math>.
 
I pokażemy, że skoro dla k jest prawdziwe to będzie także dla <math> k + 1 </math>, ale najpierw postawmy tę tezę.
: '''Teza indukcyjna:'''
:: <math> 1 + 2 + 3 + \dots + k + (k + 1) = \frac{(k+1)[(k+1) + 1]}{2} = \frac{(k+1)(k+2)}{2} </math>
 
No i w końcu przedstawimy dowód.
: '''Dowód tezy indukcyjnej:'''
:: <math> L = {\color[rgb]{0.0,0.0,0.6}1 + 2 + 3 + \dots + k} + (k+1) = {\color[rgb]{0.0,0.0,0.6}\frac{k(k+1)}{2}} + (k+1) </math>
:: <math> = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+2)(k+1)}{2} </math>
:: <math> P = \frac{(k+1)(k+2)}{2} </math>