Indukcja matematyczna
- 2. Oblicz sum 1+3+5+ . . . +(2n 1). Widzimy, 甜e dla n = 1 ostatnim skadnikiem powy甜szej sumy jest 1 (2n 1 = 1), czyli suma skada si tylko z jednego skadnika: 1. Jeli wprowadzimy oznaczenie Sn = 1 + 3 + 5 + . . . + (2n 1), to mo甜emy napisa: S1 = 1. Wida, 甜e S2 = 1 + 3 = 4, S3 = 1 + 3 + 5 = 9. Mo甜na policzy, 甜e S4 = 16, S5 = 25, a nawet S6 = 36. Widzimy ju甜, 甜e powinno by Sn = n2.
- 3. Czy mo甜na to jako uzasadni? Trzeba si przyjrze, w jaki spos坦b otrzymujemy kolejne Sn. Na przykad, jeli mamy ju甜 S6 = 1 + 3 + 5 + 7 + 9 + 11 = 36, to S7 nie bdziemy liczyli od pocztku, tylko wykorzystamy oczywist zale甜no S7 = S6 + 13 = 36 + 13 = 49. Podobnie S8 = S7 + 15 = 49 + 15 = 64 i tak dalej. Zwr坦my uwag na to, co nale甜y doda do Sn, 甜eby otrzyma Sn+1. Ot坦甜 S = S6 + (2 揃 7 1) = 62+ 2 揃 6 + 1 = (6 + 1)2= 72 oraz S8 = S7 + (2 揃 8 1) = 72+ 2 揃 7 + 1 = (7 + 1)2= 82
- 4. I tu dopiero mamy pewno, 甜e mo甜na to cign dalej i zawsze bdzie Sn = n2. Nasza pewno bierze si std, 甜e jeli Sn = n2, to Sn+1 = Sn +(2 揃(n + 1) 1) = n2+ 2n +1 = (n + 1)2. Ten ostatni rachunek pokazuje, 甜e dla ka甜dego n zachodzi implikacja: Sn = n2 Sn+1 = (n + 1)2. Oznacza to, 甜e prawdziwe s nastpujce implikacje: S1 =12 S2 =22, S2 =22 S3 =32, S3 =32 S4 =42, Jeli zatem sprawdzimy, 甜e S1 = 12, to z tego bdzie wynikaa r坦wno S2 = 22, a z tego z kolei bdzie wynikao, 甜e S3 = 32, i tak dalej dla kolejnych liczb naturalnych.
- 5. Podsumujmy nasze obserwacje. Jeli chcemy udowodni r坦wno Sn = n2 dla dowolnego naturalnego n > 1, to wystarczy sprawdzi dwie rzeczy : (I) S1 = 12. (II) Dla ka甜dego naturalnego n > 1 zachodzi implikacja Sn = n2 Sn+1 = (n + 1)2.
- 6. Co to jest indukcja matematyczna? Indukcja matematyczna, zwana te甜 indukcj zupen, jest metod dowodzenia twierdze o liczbach naturalnych. Niech T(n) oznacza form zdaniow zmiennej n okrelon w dziedzinie . Jeli w miejsce n podstawimy dowoln liczb naturaln, to T(n) stanie si zdaniem prawdziwym albo faszywym, zale甜nie od wartoci n.
- 7. Je甜eli, na przykad, T(n) oznacza wypowied添 "n jest podzielne przez 3", to T(6) jest zdaniem prawdziwym, natomiast T(7) jest zdaniem faszywym. Je甜eli T(n) oznacza nier坦wno n < n2, to T(n) jest zdaniem prawdziwym dla ka甜dej liczby naturalnej wikszej od 1, natomiast zdanie T(1) jest faszywe.
- 8. Zasada indukcji matematycznej Je甜eli: 1.istnieje taka liczba naturalna n0, 甜e T(n0) jest zdaniem prawdziwym, 2.dla ka甜dej liczby naturalnej nn0 prawdziwa jest implikacja T(n)T(n + 1), toT(n)jestzdaniemprawdziwymdlaka甜dej liczbynaturalnejnヂn0.
- 9. Udowodnij, 甜e dla ka甜dej liczby naturalnej n3 speniona jest nier坦wno 2n>2n Nier坦wno jest tu form zdaniow T(n), n0 = 3. Dla n = 3 nier坦wno jest prawdziwa, poniewa甜 23 = 8 > 2*3 = 6. T(3) jest wic zdaniem prawdziwym. 2. Za坦甜my, 甜e nier坦wno jest prawdziwa dla liczby naturalnej n 3. Mno甜c t nier坦wno obustronnie przez 2 dostajemy 2*2n > 2*2n, czyli 2n+1> 2n + 2n. Poniewa甜 dla ka甜dego n3 mamy 2n > 2, wic 2n + 2n > 2n + 2 = 2 (n + 1).
- 10. Std ostatecznie 2n+1 > 2(n + 1). Nier坦wno ta oznacza prawdziwo zdania T(n + 1). Wykazalimy zatem, 甜e dla ka甜dej liczby naturalnej n 3 prawdziwa jest implikacja T(n)T(n + 1), gdy甜 z prawdziwoci jej poprzednika wynika prawdziwo nastpnika. Zao甜enia zasady indukcji matematycznej s dla nier坦wnoci spenione. Nier坦wno ta jest prawdziwa dla ka甜dego n 3.
- 11. Dow坦d przeprowadzony metod indukcji matematycznej nazywamy dowodem indukcyjnym; skada si on z dw坦ch etap坦w: 1. sprawdzenia, 甜e T(n0) jest prawdziwe, 2. dowodu, 甜e dla ka甜dego n n0 je甜eli T(n) jest prawdziwe, to T(n + 1) jest prawdziwe. Ten drugi etap nazywamy krokiem indukcyjnym; zakadamy w nim, 甜e dla liczby naturalnej n n0 zdanie T(n) jest prawdziwe i na tej podstawie dowodzimy prawdziwoci zdania T(n + 1).
- 12. Udowodnij, 甜e dla dowolnej liczby naturalnej n > 1 zachodzi r坦wno:1揃2+2揃3+3揃4+...+n揃(n +1) =n揃(n+1)揃(n+2)/3 Rozwizanie: (I) Baza indukcji. Dla n = 1 r坦wno jest oczywista:1 揃2 =1揃2揃3/3 (II) Krok indukcyjny. Niech n bdzie dowoln liczb naturaln. Za坦甜my, 甜e dana w zadaniu r坦wno zachodzi dla n: 1 揃 2 + . . . + n 揃 (n + 1) =n 揃 (n + 1) 揃 (n + 2)/3.
- 13. W坦wczas dla n + 1 mamy: 1 揃 2 + . . . + n 揃 (n + 1) + (n + 1) 揃 (n + 2)= =n 揃 (n + 1) 揃 (n + 2)/3+ (n + 1) 揃 (n + 2) = =(n + 1) 揃 (n + 2) (n/3+ 1)= =(n + 1) 揃 (n + 2) 揃 (n + 3)/3, czyli dla n + 1 r坦wno jest prawdziwa. Na mocy zasady indukcji matematycznej r坦wno 1揃2+ 2揃3+ ...+n 揃(n + 1) =n 揃(n + 1) 揃(n + 2)/3 zachodzi dla dowolnego naturalnego n > 1.
- 14. Niech n bdzie dowoln liczb naturaln. Wyka甜, 甜e liczba 22n+1 + 3n + 7 jest podzielna przez 9 Rozwizanie: Dla n = 0 mamy liczb 22揃0+1 +3 揃0 +7 =9, kt坦ra jest, oczywicie, podzielna przez 9. Niech n bdzie dowoln liczb naturaln. Za坦甜my, 甜e dla n twierdzenie jest prawdziwe, czyli liczba 22n+1 + 3n + 7 jest podzielna przez 9. W坦wczas 22(n+1)+1+3(n+ 1)+7=22n+3+3n+3+7= =4揃22n+1+3n+10=4揃(22n+1+ 3n+ 7)9n18.
- 15. Liczby 9n i 18 s podzielne przez 9, liczba 22n+1 + 3n + 7 te甜, wic liczba 22(n+1)+1 + 3(n + 1) + 7 r坦wnie甜 jest podzielna przez 9, czyli dla n + 1 twierdzenie jest prawdziwe. Na mocy indukcji matematycznej liczba 22n+1 + 3n + 7 jest podzielna przez 9 dla dowolnego naturalnego n.
- 16. Dzikuj za uwag Dagmara Moskwa Kl IIg 2011/2012r. I LO im. Mikoaja Kopernika w Jarosawiu