Matura z matematyki - ~ Indukcja matemaczna

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. $k = 30$ ), najpierw dodajemy k-1 jedynek (np. $k - 1 = 30 - 1 = 29$ ), a potem jeszcze jedną, czyli:

S 1 = 1

S k = S k - 1 + 1

np.

S 30 = S 29 + 1

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ę:

S 1 = 1

. Dodając jedną jedynkę otrzymujemy po prostu 1, czyli wszystko OK.

Możemy jeszcze sprawdzić dla dwójki:

S 2 = 1 + 1 = 2

i znowu się zgadza.

Czyli pewnie wzór będzie się zgadzał dla wszystkich liczb $i in {1, 2, ..., 10}$ , czy też nawet dla $i in {1, 2, ..., k}$ (dla pewnego określonego k np. równego 50), co zapiszemy:

$S_i = i mbox{ dla } i in {1, 2, ..., k}$ (nasze założenie)

Czy wzór będzie się zgadzał dla $i = k + 1$ ? Sprawdźmy:

$S_i = S_{k+1} = {color[rgb]{0.0,0.0,0.6}S_k} + 1$ (skorzystaliśmy ze wzoru

S i = S i - 1 + 1

Wiemy z założenia przedstawionego ciut wyżej, że ${color[rgb]{0.0,0.0,0.6}S_k = k}$ , zatem:

$S_{k+1} = {color[rgb]{0.0,0.0,0.6} k} + 1 = k + 1$ .

Czyli do zbioru dla którego nasze twierdzenie jest prawdziwe ${1,2,..., k}$ 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 $1 + 2 + 3 + dots + n = frac{n(n+1)}{2}$ .

Najpierw musimy sprawdzić dla n=1:

$L = 1$ , ponieważ dodaliśmy tylko jedną liczbę -- 1.

$P = frac{1cdot(1+1)}{2} = 1$ .

Zgadza się, $L = P$ .

Czyli teraz możemy stworzyć odpowiednie założenie.

Założenie indukcyjne dla n = k:

${color[rgb]{0.0,0.0,0.6}1 + 2 + 3 + dots + k = frac{k(k+1)}{2}}$ .

I pokażemy, że skoro dla k jest prawdziwe to będzie także dla $k + 1$ , ale najpierw postawmy tę tezę.

Teza indukcyjna:
$1 + 2 + 3 + dots + k + (k + 1) = frac{(k+1)[(k+1) + 1]}{2} = frac{(k+1)(k+2)}{2}$

No i w końcu przedstawimy dowód.

Dowód tezy indukcyjnej:

$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)$

$= frac{k(k+1) + 2(k+1)}{2} = frac{(k+2)(k+1)}{2}$

$P = frac{(k+1)(k+2)}{2}$

Czyli $L = P$ .

Ponieważ stwierdziliśmy, że wzór jest prawdziwy dla $n = 1$ , a także z prawdziwości wzoru dla $n = k$ wynika prawdziwość wzoru dla $n = k + 1$ , więc dzięki zasadzie indukcji matematycznej wzór jest prawdziwy dla każdego całkowitego $n geq 1$ .