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

Usunięta treść Dodana treść
Piotr (dyskusja | edycje)
Piotr (dyskusja | edycje)
Linia 55:
 
== 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!
 
 
<noinclude>