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 ={1,2,3,}\mathbb{N} = \{1, 2, 3,\ldots\} skup prirodnih brojeva. Ako za podskup SS\subseteq\mathbb{N} vrijede slijedeća dva svojstva

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

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

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

Pojašnjenje i formulacija preko tvrdnji

Skupovi SS\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)P(n) tvrdnja da broj nn ima to svojstvo tada je sa

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

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

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

Primjer: formula za Fibonaccijeve brojeve

Promatrajmo Fibonaccijev niz brojeva 1,1,2,3,5,8,13,21,1, 1, 2, 3, 5, 8, 13, 21,\ldots koji je zadan tako da su prva dva broja 11, a svaki slijedeći u nizu je zbroj prethodna dva, tj. F 1=F 2=1F_1=F_2=1 i F n+2=F n+F n+1F_{n+2} = F_n+F_{n+1} za sve nn\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 nn-ti član niza je jednak

F n=15((1+52) n(152) n) 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 1+52\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=1n = 1 očito je F n=1/5(1+52152)5=55=1F_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=2n = 2 je račun također jednostavan.

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

F n+2=F n+F n+1=15[(1+52) n(152) n+(1+52) n+1(152) n+1] 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=15[(1+52) n(1+1+52)(152) n(1+152)] 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=15[(1+52) n(1+25+54)(152) n(125+54)] 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=15[(1+52) n+2(152) n+2] 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

137+1711+11115++1(4n1)(4n+3)=n3(4n+3) \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, i=1 n1(4i1)(4i3)=n3(4n+3)=S n\sum_{i = 1}^n\frac{1}{(4i-1)(4i-3)} = \frac{n}{3\cdot(4n+3)} = S_n.

Rješenje:

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

Korak indukcije: pretpostavimo da identitet vrijedi za neki nn. Tada je u tvrdnji za (n+1)(n+1) suma S n+1S_{n+1} s lijeve strane veća od S nS_n za još jedan pribrojnik, a taj je 1(4(n+1)1)(4(n+1)+3)=1(4n+3)(4n+7)\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,

1(4n+3)(4n+7)+n3(4n+3)=3+n(4n+7)3(4n+3)(4n+7)=4n 2+7n+33(4n+3)(4n+7) \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

4n 2+7n+3=4n 2+4n+3n+3=4n(n+1)+3(n+1)=(4n+3)(n+1)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

(4n+3)(n+1)3(4n+3)(4n+7)=n+13(4n+7)=n+13(4(n+1)+3)=S n+1 \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 n2n\geq 2 vrijedi nejednakost

4 n<5 n2 2n2 4^n \lt 5^n - 2^{2 n-2}

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

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

4 n+1=4(5 n2 2n2)=45 n2 22 2n2=45 n2 2n<55 n2 2n=5 n+12 2(n+1)2, 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<5 n+12 2(n+1)24^{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 nn, broj s n=n 2+ns_n = n^2 + n paran, tj. 2|(n 2+n)2|(n^2 + n).

Baza indukcije. 1 2+1=21^2 +1 = 2 pa 2|s 12| s_1.

Korak indukcije. Pretpostavimo da 2|n 2+n2| n^2 + n, dakle postoji prirodni broj kk takav da n 2+n=2kn^2 + n = 2 k. Promatrajmo sad s n+1=(n+1) 2+(n+1)=n 2+2n+1+n+1=(n 2+n)+2n+2=2k+2n+2=2(k+n+2)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+1s_{n+1} je također paran broj.

Zadaci s indukcijom

11. Dokaži indukcijom po nn da je

12+23+34+.....+n(n+1)=n(n+1)(n+2)3 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + ..... + n\cdot (n + 1) = \frac{n(n + 1)(n + 2)}{3}

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

22. Dokaži da je za svaki prirodni broj n3n\geq 3 umnožak

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

33. (a) Pokaži indukcijom po n3n\geq 3

(1+13)(1+14)(1+1n)=n+13 \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 nn\in\mathbb{N} vrijedi

(1+21)(1+23)(1+22n+1)=2n+3 \left(1 + \frac{2}{1}\right)\left(1+\frac{2}{3}\right)\cdots\left(1 +\frac{2}{2n+1}\right) = 2n+3

44. Indukcijom po nn pokaži identitet

112+123+134+.....+nn(n+1)=nn+1 \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + ..... + \frac{n}{n\cdot (n + 1)} = \frac{n}{n + 1}

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

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

55. Indukcijom po nn pokaži identitet

113+135++1(2n1)(2n+1)=n2n+1 \frac{1}{1\cdot 3} + \frac{1}{3\cdot 5} +\ldots +\frac{1}{(2n-1)\cdot (2n+1)} = \frac{n}{2n+1}

category: zadarmat1

Last revised on September 8, 2017 at 09:13:25. See the history of this page for a list of all contributions to it.