Zoran Skoda matematička indukcija

Princip matematičke indukcije je jedno svojstvo skupa prirodnih brojeva. Ubraja se među Dedekind-Peanove aksiome skupa prirodnih brojeva. Pomoću principa matematičke indukcije dokazuje se teorem o primitivnoj rekurziji koji govori o mogućnosti rekurzivnog definiranja funkcija na skupu prirodnih brojeva.

Princip (aksiom) matematičke indukcije

Označimo, kao obično, s $\mathbb{N} = \{1, 2, 3,\ldots\}$ skup prirodnih brojeva. Ako za podskup $S\subseteq\mathbb{N}$ vrijede slijedeća dva svojstva

(1) (baza indukcije) $1\in S$,

(2) (korak indukcije) Za svaki prirodni broj $n$ vrijedi da ako je $n\in S$ tada je $(n+1)\in S$,

(dakle, ako oba svojstva vrijede) tada je $S = \mathbb{N}$. Ovdje bismo zapravo trebali pisati $s(n)$ (sljedbenik od $n$) umjesto $(n+1)$, jer zbrajanje definiramo uz pomoć indukcije, pa zasad znamo samo funkciju brojenja, tj. sljedbenika, a zbrajanje s drugim pribrojnikom većim od $1$ definiramo kasnije.

Pojašnjenje i formulacija preko tvrdnji

Skupovi $S\subset \mathbb{N}$ se mogu promatrati kao svojstva elemenata od $\mathbb{N}$ (pri čemu gledamo odlučiva svojstva u smislu da element ili ima ili nema to svojstvo). Zaista ako je $P(n)$ tvrdnja da broj $n$ ima to svojstvo tada je sa

$$S_P = \{ n\in \mathbb{N} \,|\, P(n) \}$$

dan neki podskup $S_P\subseteq\mathbb{N}$. Riječima, $S_P$ je skup svih prirodnih brojevi za koje je tvrdnja $P(n)$ točna. S druge strane, ako je $S$ neki skup prirodnih brojeva, tada možemo zadati svojstvo $P_S$ prirodnih brojeva koje je po definiciji zadovoljeno za broj $n$ (tj. $P_S(n)$ je istina) akko $n\in S$. U terminima svojstva $P$ možemo princip matematičke indukcije iskazati ovako:

Neka je $P$ neko svojstvo prirodnih brojeva, tj. za svaki $n\in\mathbb{N}$ ili vrijedi $P(n)$ ili nije $P(n)$. Ako vrijedi $P(1)$ (“baza indukcije”) i ako za svaki $n\in\mathbb{N}$ iz $P(n)$ slijedi $P(s(n))$ (“korak indukcije”), tada vrijedi $P(n)$ za sve $n\in\mathbb{N}$.

Prednost te formulacije je da ne koristi pojam skupa, tj. u sklopu je formulacije Peanovih aksioma koja ne koristi skupove (za sve Peanove aksiome vidi prirodni broj).

Primjer: formula za Fibonaccijeve brojeve

Promatrajmo Fibonaccijev niz brojeva $1, 1, 2, 3, 5, 8, 13, 21,\ldots$ koji je zadan tako da su prva dva broja $1$, a svaki slijedeći u nizu je zbroj prethodna dva, tj. $F_1=F_2=1$ i $F_{n+2} = F_n+F_{n+1}$ za sve $n\in\mathbb{N}$. To je rekurzivna definicija, a sam pojam rekurzivne definicije opravdan je na temelju matematičke indukcije. No, važnije je da se u praksi matematičkom indukcijom često mogu dokazivati tvrdnje o formuli za opći član niza. Tvrdnja: u Fibonaccijevom nizu $n$-ti član niza je jednak

$$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$

Leonardo da Vinci nazva omjer $\frac{1+\sqrt{5}}{2}$ zlatnim rezom jer se pojavljuje u mnogim geometrijskim proporcijama u prirodi i umjetnosti.

Dokaz je preko matematičke indukcije. Baza indukcije. Za $n = 1$ očito je $F_n = 1/\sqrt{5}\left( \frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}\right)\sqrt{5} = \frac{\sqrt{5}}{\sqrt{5}} = 1$. Za $n = 2$ je račun također jednostavan.

Korak indukcije: pretpostavimo da tvrdnja vrijedi za neki $n\in\mathbb{N}$ i $(n+1)\in\mathbb{N}$. Dokažimo da vrijedi za $(n+2)$.

$$F_{n+2} = F_{n}+F_{n+1} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n +\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right]$$

Ako dodamo prvi pribrojnik trećem i drugi četvrtom dobivamo

$$F_{n+2} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n\left(1 + \frac{1+\sqrt{5}}{2}\right)- \left(\frac{1-\sqrt{5}}{2}\right)^n \left(1+\frac{1-\sqrt{5}}{2}\right) \right]$$

$$F_{n+2} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^n\left(\frac{1+2\sqrt{5}+5}{4}\right)- \left(\frac{1-\sqrt{5}}{2}\right)^n \left(\frac{1-2\sqrt{5}+5}{4}\right) \right]$$

$$F_{n+2} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \right]$$

Primjer indukcije

Dokaži da

$$\frac{1}{3\cdot 7} +\frac{1}{7\cdot 11} +\frac{1}{11\cdot 15} +\ldots + \frac{1}{(4n-1)(4n+3)} = \frac{n}{3(4n+3)}$$

Dakle, $\sum_{i = 1}^n\frac{1}{(4i-1)(4i-3)} = \frac{n}{3\cdot(4n+3)} = S_n$.

Rješenje:

Baza indukcije: za $n=1$ lijeva strana je $1/21$ a desna je $\frac{1}{(4\cdot 1-1)(4\cdot 1+3)} = \frac{1}{21}$.

Korak indukcije: pretpostavimo da identitet vrijedi za neki $n$. Tada je u tvrdnji za $(n+1)$ suma $S_{n+1}$ s lijeve strane veća od $S_n$ za još jedan pribrojnik, a taj je $\frac{1}{(4(n+1)-1)(4(n+1)+3)} = \frac{1}{(4n+3)(4n+7)}$. Dakle identitet vrijedi akko je i suma s desne strane povećana za isti izraz. No,

$$\frac{1}{(4n+3)(4n+7)} + \frac{n}{3(4n+3)} = \frac{3 + n(4n + 7)}{3(4n+3)(4n+7)} = \frac{4 n^2 + 7n + 3}{3(4n+3)(4n+7)}$$

Sad rastavimo brojnik kao

$4 n^2 + 7n + 3 = 4 n^2 + 4 n + 3n + 3 = 4n (n+1) + 3(n+1) = (4n +3)(n+1)$ i dobijemo da je desna strana zadnje jednakosti

$$\frac{(4n +3)(n+1)}{3(4n+3)(4n+7)} = \frac{n+1}{3(4n+7)} = \frac{n+1}{3(4(n+1)+3)} = S_{n+1}$$

kako smo i trebali dokazati.

Primjer s nejednakosti

Dokaži da je za $n\geq 2$ vrijedi nejednakost

$$4^n \lt 5^n - 2^{2 n-2}$$

(za $n=1$ vrijedi jednakost $4^1 = 5^1 - 2^{2\cdot 0}$).

Baza indukcije je za $n=2$ kad je $4^2 = 16 \lt 21 = 25 -4 = 5^2 - 2^{2\cdot 2-2}$. Pretpostavimo da nejednakost vrijedi za $n$. Tada

$$4^{n+1} = 4\cdot (5^n - 2^{2n-2}) = 4\cdot 5^n - 2^2 \cdot 2^{2n-2} = 4\cdot 5^n - 2^{2n} \lt 5\cdot 5^n - 2^{2n} = 5^{n+1} - 2^{2(n+1)-2},$$

dakle, $4^{n+1}\lt 5^{n+1} - 2^{2(n+1)-2}$, kako smo i tražili.

Primjer s djeljivošću

Pokaži da je za svaki prirodni broj $n$, broj $s_n = n^2 + n$ paran, tj. $2|(n^2 + n)$.

Baza indukcije. $1^2 +1 = 2$ pa $2| s_1$.

Korak indukcije. Pretpostavimo da $2| n^2 + n$, dakle postoji prirodni broj $k$ takav da $n^2 + n = 2 k$. Promatrajmo sad $s_{n+1} = (n+1)^2 + (n+1) = n^2 + 2 n + 1 + n + 1 = (n^2 + n) + 2n +2 = 2k + 2n + 2 = 2 (k+n+2)$, dakle $s_{n+1}$ je također paran broj.

Zadaci s indukcijom

$1$. Dokaži indukcijom po $n$ da je

$$1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + ..... + n\cdot (n + 1) = \frac{n(n + 1)(n + 2)}{3}$$

Simbolički $\sum_{i = 1}^n i\cdot(i+1) = \frac{n(n + 1)(n + 2)}{3}$.

$2$. Dokaži da je za svaki prirodni broj $n\geq 3$ umnožak

$$\left(1 -\frac{1}{3}\right)\left(1-\frac{1}{4}\right)\cdots\left(1 - \frac{1}{n}\right) = \frac{2}{n}$$

$3$. (a) Pokaži indukcijom po $n\geq 3$

$$\left(1 +\frac{1}{3}\right)\left(1+\frac{1}{4}\right)\cdots\left(1+\frac{1}{n}\right) = \frac{n+1}{3}$$

(b) Pokaži da za svaki $n\in\mathbb{N}_0$ vrijedi

$$\left(1 + \frac{2}{1}\right)\left(1+\frac{2}{3}\right)\cdots\left(1 +\frac{2}{2n+1}\right) = 2n+3$$

S lijeve strane je $(n+1)$ množitelja.

$4$. Indukcijom po $n$ pokaži identitet

$$\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + ..... + \frac{1}{n\cdot (n + 1)} = \frac{n}{n + 1}$$

Izrazivši zbroj s lijeve strane simbolički, taj identitet kaže

$$\sum_{i = 1}^n \frac{1}{i\cdot(i+1)} = \frac{n}{n+1}$$

$5$. Indukcijom po $n$ pokaži identitet

$$\frac{1}{1\cdot 3} + \frac{1}{3\cdot 5} +\ldots +\frac{1}{(2n-1)\cdot (2n+1)} = \frac{n}{2n+1}$$

$6.$ Dokaži matematičkom indukcijom da vrijedi za sve $k = 2, 3, 4,\ldots$

$$\left( 1 - \frac{1}{2^2} \right)\cdot \left( 1 - \frac{1}{3^2} \right) \cdots \left( 1 - \frac{1}{k^2} \right) = \frac{1}{2} + \frac{1}{2 k}$$

S lijeve strane jednakosti se množi $(k-1)$ množitelja.

category: zadarmat1