Matematyka dla liceum/Ciągi liczbowe/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ą.

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.

Najprościej mówiąc, rekurencja tak w matematyce jak i w informatyce, to odwoływanie się funkcji (ciągu, algorytmu) do samej siebie. Ze wzorem rekurencyjnym mamy więc do czynienia wtedy, gdy w definicji wyrazu n-tego mamy odwołanie do wyrazu o indeksie w jakiś sposób zależnym od n, na przykład do wyrazu o indeksie n-1 (czyli wyrazu poprzedniego).

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}{\mbox{ 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 jest napisane 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:

1. Pokazaliśmy, że jest prawdziwe dla 1.
2. Założyliśmy, że w takim razie będzie prawdziwe dla 1, 2, 3, ..., k.
3. Pokazaliśmy, że skoro jest prawdziwe od 1 do k, więc musi być także prawdziwe dla k + 1.
4. 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 {1\cdot (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$.