Matematička indukcija - zadaci sa rešenjima

Rešenje:
Pošto je [tex]1+2+\ldots+n=\frac{n(n+1)}{2}[/tex] (zbir aritmetičke progresije), dovoljno je dokazati da je
[tex]S_{n}=1^{3}+2^{3}+\ldots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}[/tex]
Primenimo matematičku indukciju po [tex]n[/tex]. Baza indukcije: za [tex]n=1[/tex] imamo [tex]S_{1}=1=\frac{1^{2}\cdot 2^{2}}{4}[/tex].
Induktivni korak: pretpostavimo da je [tex]S_{k}=\frac{k^{2}(k+1)^{2}}{4}[/tex] za neki prirodan broj [tex]k[/tex]. Tada je
[tex]S_{k+1}=S_{k}+(k+1)^{3}=\frac{k^{2}(k+1)^{2}}{4}+(k+1)^{3}=\frac{(k+1)^{2}\left(k^{2}+4k+4\right)}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}[/tex]
tj. formula važi i za [tex]n=k+1[/tex]. Prema principu matematičke indukcije, za svaki prirodan broj [tex]n[/tex] važi
[tex]1^{3}+2^{3}+\ldots+n^{3}=\left(\frac{n(n+1)}{2}\right)^{2}=\left(1+2+\ldots+n\right)^{2}[/tex]

Rešenje:
Fiksirajmo [tex]x\ge -1[/tex] i primenimo indukciju po [tex]n[/tex]. Baza indukcije: za [tex]n=1[/tex] nejednakost glasi [tex]1+x\ge 1+x[/tex], što je tačno (jednakost).
Induktivni korak: pretpostavimo da je [tex]\left(1+x\right)^{k}\ge 1+kx[/tex] za neki prirodan broj [tex]k[/tex]. Pošto je [tex]x\ge -1[/tex], važi [tex]1+x\ge 0[/tex], pa množenje obe strane sa [tex]1+x[/tex] ne menja smer nejednakosti:
[tex]\left(1+x\right)^{k+1}\ge (1+kx)(1+x)=1+(k+1)x+kx^{2}\ge 1+(k+1)x[/tex]
jer je [tex]kx^{2}\ge 0[/tex]. To je nejednakost za [tex]n=k+1[/tex], pa prema principu matematičke indukcije ona važi za svaki prirodan broj [tex]n[/tex]. Uslov [tex]x\ge -1[/tex] je upravo ono što dozvoljava množenje sa [tex]1+x[/tex].

Rešenje:
Neka je [tex]A_{n}=4^{n}+15n-1[/tex]. Primenimo indukciju po [tex]n[/tex]. Baza indukcije: [tex]A_{1}=4+15-1=18=9\cdot 2[/tex] je deljivo sa [tex]9[/tex].
Induktivni korak: pretpostavimo da je [tex]A_{k}[/tex] deljivo sa [tex]9[/tex] za neki prirodan broj [tex]k[/tex]. Izrazimo [tex]A_{k+1}[/tex] preko [tex]A_{k}[/tex]:
[tex]A_{k+1}=4\cdot 4^{k}+15k+14=4\left(4^{k}+15k-1\right)-45k+18=4A_{k}-9(5k-2)[/tex]
Broj [tex]4A_{k}[/tex] je deljiv sa [tex]9[/tex] prema induktivnoj pretpostavci, a [tex]9(5k-2)[/tex] je umnožak broja [tex]9[/tex], pa je i [tex]A_{k+1}[/tex] deljivo sa [tex]9[/tex]. Prema principu matematičke indukcije, broj [tex]4^{n}+15n-1[/tex] je deljiv sa [tex]9[/tex] za svaki prirodan broj [tex]n[/tex].

Rešenje:
Izračunajmo prve vrednosti:
[tex]P_{2}=\frac{3}{4}; \quad P_{3}=\frac{3}{4}\cdot \frac{8}{9}=\frac{2}{3}=\frac{4}{6}; \quad P_{4}=\frac{2}{3}\cdot \frac{15}{16}=\frac{5}{8}[/tex]
Vrednosti [tex]\frac{3}{4}[/tex], [tex]\frac{4}{6}[/tex], [tex]\frac{5}{8}[/tex] navode na pretpostavku da je [tex]P_{n}=\frac{n+1}{2n}[/tex]. Dokažimo to indukcijom za [tex]n\ge 2[/tex]. Baza indukcije: [tex]P_{2}=\frac{3}{4}=\frac{2+1}{2\cdot 2}[/tex].
Induktivni korak: pretpostavimo da je [tex]P_{k}=\frac{k+1}{2k}[/tex] za neko [tex]k\ge 2[/tex]. Tada je
[tex]P_{k+1}=P_{k}\left(1-\frac{1}{(k+1)^{2}}\right)=\frac{k+1}{2k}\cdot \frac{k(k+2)}{(k+1)^{2}}=\frac{k+2}{2(k+1)}[/tex]
tj. formula važi i za [tex]n=k+1[/tex]. Dakle, [tex]P_{n}=\frac{n+1}{2n}[/tex] za svako [tex]n\ge 2[/tex].
Formule [tex]\frac{n+1}{n+2}[/tex] i [tex]\frac{n^{2}-1}{n^{2}}[/tex] daju tačnu vrednost [tex]P_{2}=\frac{3}{4}[/tex], ali ne važe već za [tex]n=3[/tex], a formula [tex]\frac{n+2}{2(n+1)}[/tex] je pomerena za jedan indeks (jednaka je [tex]P_{n+1}[/tex]).

Rešenje:
Svaki član je određen sa dva prethodna, pa proveravamo dve početne vrednosti i pretpostavljamo da formula važi za dva uzastopna indeksa. Baza indukcije: za [tex]n=1[/tex] i [tex]n=2[/tex]:
[tex]3\cdot 2^{0}+2\cdot (-1)^{1}=1=a_{1}; \quad 3\cdot 2^{1}+2\cdot (-1)^{2}=8=a_{2}[/tex]
Induktivni korak: pretpostavimo da za neko [tex]k\ge 3[/tex] formula važi za [tex]n=k-2[/tex] i [tex]n=k-1[/tex]. Koristeći [tex](-1)^{k-1}=-(-1)^{k}[/tex] i [tex](-1)^{k-2}=(-1)^{k}[/tex], dobijamo
[tex]a_{k}=a_{k-1}+2a_{k-2}=3\cdot 2^{k-2}+2(-1)^{k-1}+2\left(3\cdot 2^{k-3}+2(-1)^{k-2}\right)[/tex]
[tex]=3\cdot 2^{k-2}+3\cdot 2^{k-2}+(-1)^{k}(-2+4)=3\cdot 2^{k-1}+2\cdot (-1)^{k}[/tex]
Dakle, formula važi i za [tex]n=k[/tex], pa prema principu matematičke indukcije važi za svaki prirodan broj [tex]n[/tex].

Rešenje:
Neka je [tex]S_{n}[/tex] leva strana; ona se sastoji od [tex]2n+1[/tex] sabiraka od [tex]\frac{1}{n+1}[/tex] do [tex]\frac{1}{3n+1}[/tex]. Primenimo indukciju po [tex]n[/tex]. Baza indukcije:
[tex]S_{1}=\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{13}{12}\gt 1[/tex]
Induktivni korak: pretpostavimo da je [tex]S_{k}\gt 1[/tex] za neki prirodan broj [tex]k[/tex]. U poređenju sa [tex]S_{k}[/tex], u zbiru [tex]S_{k+1}=\frac{1}{k+2}+\ldots+\frac{1}{3k+4}[/tex] nestaje sabirak [tex]\frac{1}{k+1}[/tex], a dodaju se tri sabirka [tex]\frac{1}{3k+2}[/tex], [tex]\frac{1}{3k+3}[/tex], [tex]\frac{1}{3k+4}[/tex]:
[tex]S_{k+1}=S_{k}+\frac{1}{3k+2}+\frac{1}{3k+3}+\frac{1}{3k+4}-\frac{1}{k+1}[/tex]
Pošto je [tex]\frac{1}{k+1}=\frac{3}{3k+3}[/tex], za [tex]m=3k+3[/tex] dobijamo
[tex]S_{k+1}-S_{k}=\frac{1}{m-1}+\frac{1}{m+1}-\frac{2}{m}=\frac{2m}{m^{2}-1}-\frac{2}{m}=\frac{2}{m\left(m^{2}-1\right)}\gt 0[/tex]
jer je [tex]m\ge 6[/tex]. Dakle, [tex]S_{k+1}\gt S_{k}\gt 1[/tex], pa prema principu matematičke indukcije nejednakost važi za svaki prirodan broj [tex]n[/tex].

Rešenje:
Primenimo indukciju po [tex]n[/tex] (istovremeno za sve [tex]x[/tex]). Baza indukcije: za [tex]n=1[/tex] nejednakost glasi [tex]\left|\sin x\right|\le\left|\sin x\right|[/tex], što je tačno.
Induktivni korak: pretpostavimo da je [tex]\left|\sin kx\right|\le k\left|\sin x\right|[/tex] za neki prirodan broj [tex]k[/tex] i svaki realan broj [tex]x[/tex]. Prema adicionoj formuli za sinus
[tex]\sin (k+1)x=\sin kx\cos x+\cos kx\sin x[/tex]
Iz nejednakosti trougla, ocena [tex]\left|\cos x\right|\le 1[/tex], [tex]\left|\cos kx\right|\le 1[/tex] i induktivne pretpostavke sledi
[tex]\left|\sin (k+1)x\right|\le\left|\sin kx\right|\left|\cos x\right|+\left|\cos kx\right|\left|\sin x\right|\le\left|\sin kx\right|+\left|\sin x\right|[/tex]
[tex]\le k\left|\sin x\right|+\left|\sin x\right|=(k+1)\left|\sin x\right|[/tex]
To je nejednakost za [tex]n=k+1[/tex], pa prema principu matematičke indukcije ona važi za svaki prirodan broj [tex]n[/tex] i svaki realan broj [tex]x[/tex].

Rešenje:
Neka je [tex]z_{n}=x^{n}+\frac{1}{x^{n}}[/tex]. Prema uslovu [tex]z_{1}[/tex] je ceo broj, a
[tex]z_{2}=\left(x+\frac{1}{x}\right)^{2}-2=z_{1}^{2}-2[/tex]
je takođe ceo broj. Za svaki prirodan broj [tex]n\ge 2[/tex] važi
[tex]z_{1}z_{n}=\left(x+\frac{1}{x}\right)\left(x^{n}+\frac{1}{x^{n}}\right)=x^{n+1}+\frac{1}{x^{n+1}}+x^{n-1}+\frac{1}{x^{n-1}}=z_{n+1}+z_{n-1}[/tex]
tj.
[tex]z_{n+1}=z_{1}z_{n}-z_{n-1}[/tex]
Primenimo indukciju sa dve baze: [tex]z_{1}[/tex] i [tex]z_{2}[/tex] su celi brojevi. Induktivni korak: pretpostavimo da su [tex]z_{k-1}[/tex] i [tex]z_{k}[/tex] celi brojevi za neko [tex]k\ge 2[/tex]. Tada je [tex]z_{k+1}=z_{1}z_{k}-z_{k-1}[/tex] ceo broj kao proizvod i razlika celih brojeva. Dakle, [tex]x^{n}+\frac{1}{x^{n}}[/tex] je ceo broj za svaki prirodan broj [tex]n[/tex].

Rešenje:
Neka je [tex]R_{n}[/tex] broj delova. Jedna kružnica deli ravan na [tex]R_{1}=2[/tex] dela (unutrašnjost i spoljašnjost). Pretpostavimo da je nacrtano [tex]k\ge 1[/tex] kružnica i da dodajemo [tex](k+1)[/tex]. kružnicu. Ona seče svaku od [tex]k[/tex] starih kružnica u tačno dve tačke, pri čemu se nikoje dve od tih [tex]2k[/tex] tačaka ne poklapaju, jer nikoje tri kružnice ne prolaze kroz istu tačku. One dele novu kružnicu na [tex]2k[/tex] lukova.
Nijedan luk ne sadrži presečne tačke u svojoj unutrašnjosti, pa svaki luk leži u jednom od postojećih delova i deli ga na dva. Dakle, svaki luk dodaje tačno jedan deo:
[tex]R_{k+1}=R_{k}+2k[/tex]
Odavde dobijamo
[tex]R_{1}=2; \quad R_{2}=4; \quad R_{3}=8; \quad R_{4}=14[/tex]
i indukcijom dokazujemo da je [tex]R_{n}=n^{2}-n+2[/tex]. Baza indukcije: [tex]R_{1}=1-1+2=2[/tex]. Induktivni korak: ako je [tex]R_{k}=k^{2}-k+2[/tex] za neki prirodan broj [tex]k[/tex], onda je
[tex]R_{k+1}=k^{2}-k+2+2k=k^{2}+k+2=(k+1)^{2}-(k+1)+2[/tex]
Dakle, kružnice dele ravan na [tex]n^{2}-n+2[/tex] delova. Primetimo da se [tex]2^{n}[/tex] poklapa sa prve tri vrednosti, ali za [tex]n=4[/tex] daje [tex]16[/tex] umesto [tex]14[/tex], pa naslućenu pravilnost uvek treba dokazati.

Rešenje:
Proverimo male vrednosti. Za [tex]n=1[/tex] nejednakost [tex]2\gt 1[/tex] važi, ali za [tex]2\le n\le 9[/tex] ne važi, jer su vrednosti [tex]2^{n}[/tex] i [tex]n^{3}[/tex]
[tex]4\lt 8; \quad 8\lt 27; \quad 16\lt 64; \quad 32\lt 125; \quad 64\lt 216; \quad 128\lt 343; \quad 256\lt 512; \quad 512\lt 729[/tex]
Pošto nejednakost ne važi za [tex]n=9[/tex], mora biti [tex]n_{0}\ge 10[/tex]. Indukcijom dokazujemo da ona važi za svako [tex]n\ge 10[/tex]. Baza indukcije:
[tex]2^{10}=1024\gt 1000=10^{3}[/tex]
Induktivni korak: pretpostavimo da je [tex]2^{k}\gt k^{3}[/tex] za neko [tex]k\ge 10[/tex]. Tada je, pošto je [tex]k\ge 10[/tex],
[tex]2^{k+1}=2\cdot 2^{k}\gt 2k^{3}=k^{3}+k\cdot k^{2}\ge k^{3}+10k^{2}[/tex]
Osim toga, [tex]3k^{2}\ge 3k[/tex] i [tex]4k^{2}\ge 1[/tex], pa je
[tex]10k^{2}=3k^{2}+3k^{2}+4k^{2}\ge 3k^{2}+3k+1[/tex]
Prema tome,
[tex]2^{k+1}\gt k^{3}+3k^{2}+3k+1=(k+1)^{3}[/tex]
Dakle, nejednakost važi za svako [tex]n\ge 10[/tex], a najmanji takav broj je [tex]n_{0}=10[/tex].

Rešenje:
Iznos od [tex]k[/tex] evrocenti može se platiti tačno onda kada je [tex]k=5x+7y[/tex] sa nenegativnim celim brojevima [tex]x[/tex] i [tex]y[/tex]. Iznos [tex]23[/tex] ne može se platiti: pošto je [tex]7y\le 23[/tex], imamo [tex]y\in\left\{0; 1; 2; 3\right\}[/tex], a
[tex]23-7y\in\left\{23; 16; 9; 2\right\}[/tex]
i nijedan od tih brojeva nije deljiv sa [tex]5[/tex]. Dakle, [tex]Z\ge 24[/tex]. Indukcijom dokazujemo da se svaki iznos [tex]k\ge 24[/tex] može platiti. Baza indukcije:
[tex]24=2\cdot 5+2\cdot 7[/tex]
Induktivni korak: pretpostavimo da je [tex]k=5x+7y[/tex] sa celim brojevima [tex]x,y\ge 0[/tex] za neko [tex]k\ge 24[/tex]. Ako je [tex]y\ge 2[/tex], zamenimo dve marke od [tex]7[/tex] evrocenti ([tex]14[/tex] evrocenti) sa tri marke od [tex]5[/tex] evrocenti ([tex]15[/tex] evrocenti):
[tex]k+1=5(x+3)+7(y-2)[/tex]
Ako je [tex]y\le 1[/tex], onda je [tex]5x=k-7y\ge 24-7=17[/tex], pa je [tex]x\ge 4[/tex]; zamenimo četiri marke od [tex]5[/tex] evrocenti ([tex]20[/tex] evrocenti) sa tri marke od [tex]7[/tex] evrocenti ([tex]21[/tex] evrocent):
[tex]k+1=5(x-4)+7(y+3)[/tex]
U oba slučaja [tex]k+1[/tex] se može platiti. Dakle, svaki iznos [tex]k\ge 24[/tex] može se platiti, a [tex]23[/tex] ne može, pa je [tex]Z=24[/tex].

Rešenje:
Neka je
[tex]P_{n}=\frac{1}{2}\cdot \frac{3}{4}\cdot \ldots\cdot \frac{2n-1}{2n}[/tex]
Direktna indukcija ne prolazi: iz [tex]P_{k}\lt\frac{1}{\sqrt{3k-1}}[/tex] bilo bi potrebno da važi
[tex]\frac{2k+1}{(2k+2)\sqrt{3k-1}}\le\frac{1}{\sqrt{3k+2}}\iff(2k+1)^{2}(3k+2)\le(2k+2)^{2}(3k-1)[/tex]
[tex]\iff 12k^{3}+20k^{2}+11k+2\le 12k^{3}+20k^{2}+4k-4[/tex]
što nije tačno. Zato dokazujemo jače tvrđenje
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\qquad(*)[/tex]
za svaki prirodan broj [tex]n[/tex]; jača induktivna pretpostavka omogućava induktivni korak. Baza indukcije: [tex]P_{1}=\frac{1}{2}=\frac{1}{\sqrt{4}}[/tex].
Induktivni korak: pretpostavimo da je [tex]P_{k}\le\frac{1}{\sqrt{3k+1}}[/tex] za neki prirodan broj [tex]k[/tex]. Tada je
[tex]P_{k+1}=P_{k}\cdot \frac{2k+1}{2k+2}\le\frac{2k+1}{(2k+2)\sqrt{3k+1}}[/tex]
Dovoljno je pokazati da desna strana nije veća od [tex]\frac{1}{\sqrt{3k+4}}[/tex]. Obe strane su pozitivne, pa je to ekvivalentno nejednakosti između njihovih kvadrata:
[tex]\frac{2k+1}{(2k+2)\sqrt{3k+1}}\le\frac{1}{\sqrt{3k+4}}\iff(2k+1)^{2}(3k+4)\le(2k+2)^{2}(3k+1)[/tex]
[tex]\iff 12k^{3}+28k^{2}+19k+4\le 12k^{3}+28k^{2}+20k+4\iff 0\le k[/tex]
što je tačno. Dakle, [tex]P_{k+1}\le\frac{1}{\sqrt{3k+4}}=\frac{1}{\sqrt{3(k+1)+1}}[/tex], pa (*) važi za svaki prirodan broj [tex]n[/tex]. Najzad, za [tex]n\gt 1[/tex] imamo [tex]3n+1\gt 3n-1\gt 0[/tex], pa je
[tex]P_{n}\le\frac{1}{\sqrt{3n+1}}\lt\frac{1}{\sqrt{3n-1}}[/tex]

Rešenje:
Neka je [tex]A_{n}=82^{n+1}+(45n-82)\cdot 127^{n}[/tex] i primetimo da je [tex]127-82=45[/tex]. Primenimo indukciju po [tex]n[/tex]. Baza indukcije:
[tex]A_{1}=82^{2}+(45-82)\cdot 127=6724-4699=2025=45^{2}[/tex]
Da bismo povezali [tex]A_{k+1}[/tex] sa [tex]A_{k}[/tex], izračunajmo (koristeći [tex]45(k+1)-82=45k-37[/tex])
[tex]A_{k+1}-82A_{k}=82^{k+2}+(45k-37)\cdot 127^{k+1}-82^{k+2}-82(45k-82)\cdot 127^{k}[/tex]
[tex]=127^{k}\left[127(45k-37)-82(45k-82)\right][/tex]
Izraz u zagradi jednak je
[tex]45k(127-82)-127\cdot 37+82^{2}=45^{2}k-4699+6724=2025k+2025=45^{2}(k+1)[/tex]
Dakle,
[tex]A_{k+1}=82A_{k}+45^{2}(k+1)\cdot 127^{k}[/tex]
Induktivni korak: pretpostavimo da je [tex]A_{k}[/tex] deljivo sa [tex]45^{2}[/tex] za neki prirodan broj [tex]k[/tex]. Tada su oba sabirka na desnoj strani deljiva sa [tex]45^{2}[/tex], pa je i [tex]A_{k+1}[/tex] deljivo sa [tex]45^{2}[/tex]. Prema principu matematičke indukcije, [tex]A_{n}[/tex] je deljivo sa [tex]45^{2}[/tex] za svaki prirodan broj [tex]n[/tex].

Rešenje:
Indukcijom po [tex]n[/tex] dokazujemo da se crveni deo može prekriti za svaki položaj plavog kvadratića. Baza indukcije: za [tex]n=1[/tex] kvadrat ima stranicu [tex]2[/tex], a njegov crveni deo sastoji se od tri jedinična kvadratića koji čine tačno jedan L-trimino.
Induktivni korak: pretpostavimo da se za neki prirodan broj [tex]k[/tex] svaki kvadrat stranice [tex]2^{k}[/tex] iz kojeg je isključen jedan proizvoljan jedinični kvadratić može prekriti L-triminima. Podelimo kvadrat stranice [tex]2^{k+1}[/tex] dužima koje spajaju središta njegovih naspramnih stranica na četiri četvrtine, kvadrate stranice [tex]2^{k}[/tex]. Plavi kvadratić leži u tačno jednoj četvrtini.
Svaka od ostale tri četvrtine ima ugaoni jedinični kvadratić u centru velikog kvadrata; ta tri kvadratića čine L-trimino, i na njih postavljamo jedan trimino. Sada je svaka od četiri četvrtine kvadrat stranice [tex]2^{k}[/tex] sa tačno jednim isključenim jediničnim kvadratićem (plavim ili onim koji je pokriven centralnim triminom).
Prema induktivnoj pretpostavci svaka četvrtina može se prekriti, i zajedno sa centralnim triminom to prekriva ceo crveni deo. Dakle, tvrđenje važi za svaki prirodan broj [tex]n[/tex]. To je u skladu sa brojem crvenih kvadratića: [tex]4^{n}-1[/tex] je deljivo sa [tex]3[/tex].