Matura z matematyki - ~Rekurencja i indukcja matematyczna

Rekurencja

Ze wzorami opisywanymi rekurencyjnie spotkaliśmy się już wcześniej. Na przykład, wiemy, że dla dowolnego ciągu arytmetycznego o różnicy r=5 zachodzi:

a n + 1 = a n + 5

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:

$a_{n+1} = a_n cdot 7$ .

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 arytmetyczny $(a n)$ określony wzorem:
$a_n = left{begin{matrix} 3 & mbox{ dla } n = 1 \ a_{n-1} + 2 & mbox{ dla } n > 1 end{matrix}right.$

W tym przypadku widzimy na przykład, że:

$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$ . Wiedząc, że $a 1 = 3$ i $r = 2$ i korzystając, ze wzoru ogólnego na n-ty wyraz ciągu arytmetycznego możemy wynik $a_5 = 3 + (5-1) cdot 2 = 11$ , dochodzimy, do takiego samego wyniku.

ciąg geometryczny $(b n)$ , gdzie:
$a 1 = 10$
$a_{n+1} = a_n cdot 6 mbox{ dla } n geq 1$

W tym przypadku widzimy, że n-ty wyraz jest 6 razy większy od poprzedniego. Ze wzoru rekurencyjnego możemy wyliczyć, że:

$a_3 = a_2 cdot 6 = (a_1 cdot 6) cdot 6 = (10 cdot 6) cdot 6 = 360$ .

W poprzednim rozdziale widzieliśmy nieco skomplikowany ciąg nazywany, który jest zdefiniowany wzorem:

$F 1 = 1$
$F 2 = 1$
$F n = F n - 1 + F n - 2 dla n > 2$ .

Policzmy teraz $F 5$ :

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

Powinniśmy już pamiętać, że ciąg zdefiniowany wzorem:

a 1 = x

$a_{n+1} = a_{n} + r mbox{ dla } n geq 1$ ,

posiada postać zwartą, czyli bez rekurencji, w postaci:

$a_n = a_1 + (n-1) cdot r mbox{ dla } n geq 1$ . (Jak pamiętamy, jest to ciąg arytmetyczny.)

Natomiast postać zwarta ciągu geometrycznego zdefiniowanego wzorem:

a 1 = x

$a_{n+1} = a_n cdot q mbox{ dla } n geq 1$

będzie postaci:

$a_n = a_1 cdot q^{n-1} mbox{ dla } n geq 1$ ,

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