Matematička indukcija

Matematička indukcija je metod dokazivanja tvrđenja koja zavise od prirodnog broja $n$: formula za zbirove, deljivosti, nejednakosti. Ovde ćemo videti odakle potiče naziv metoda, zašto je metod ispravan i kako se primenjuje.

Na ovoj stranici: Nepotpuna indukcija · Potpuna indukcija · Princip matematičke indukcije · Primeri · Indukcija od ${n=m}$ · Hipoteza i dokaz · Zadaci

Nepotpuna indukcija

Metod istraživanja u kome posmatramo pojedine elemente jednog skupa i na osnovu njih otkrivamo osobine celog skupa naziva se induktivni metod. Kada nisu razmotreni svi slučajevi, kažemo da je primenjena nepotpuna indukcija.

Evo jednog primera iz istorije matematike. Francuski matematičar iz XVII veka Pjer de Ferma posmatrao je brojeve

${2^{2^1}+1=5}$, ${2^{2^2}+1=17}$, ${2^{2^3}+1=257}$, ${2^{2^4}+1=65.537}$

i primetio da su svi prosti. Pretpostavio je da je broj ${2^{2^n}+1}$ prost za svako prirodno $n$. Za ${n=5}$ dobija se ${2^{2^5}+1=4.294.967.297}$ i Ferma nije uspeo da proveri da li taj broj ima netrivijalne delioce. Kasnije je Ojler pokazao da je on deljiv sa 641: ${4.294.967.297}={641\cdot 6.700.417}$. Dakle, Fermaova pretpostavka nije tačna.

Postoje i primeri u kojima je prvi slučaj koji obara hipotezu dobijenu nepotpunom indukcijom toliko daleko da se do njega ne može stići proveravanjem. Na primer, izgleda da broj ${991n^2+1}$ nikada nije potpun kvadrat. To zaista važi za svako prirodno $n$ manje od

${n}={12.055.735.790.331}\allowbreak{.359.447.442.538.767}$,

ali za ovaj 29-cifreni broj ${991n^2+1}$ jeste potpun kvadrat. Toliko provera ne mogu da izvedu ni najbrži računari.

Ovi primeri pokazuju da zaključak zasnovan na nepotpunoj indukciji može biti netačan, pa nepotpunu indukciju treba koristiti oprezno. Ona je korisna jer posebni slučajevi nagoveštavaju zakonitost i pomažu nam da postavimo hipotezu. Tačnost hipoteze, međutim, mora da se dokaže na drugi način.

Potpuna indukcija

Ako posebnih slučajeva ima konačno mnogo i svi su razmotreni, zaključak je zasnovan. Na primer, da bismo saznali koliko ima prostih brojeva među brojevima od 1 do 10, dovoljno je da proverimo svaki od njih: prosti su 2, 3, 5 i 7. Zaključak „u prvoj desetici ima 4 prosta broja“ ne zahteva drugo obrazloženje.

Metod u kome ispitujemo sve elemente jednog skupa i izvodimo zaključak o celom skupu naziva se potpuna indukcija. Zaključak dobijen potpunom indukcijom je potpuno pouzdan, pa je ona metod strogog dokazivanja.

Potpuna indukcija se ipak retko koristi: glomazna je kada slučajeva ima mnogo, a neprimenljiva kada ih ima beskonačno mnogo. Beskonačan skup može se njome ispitati samo ako se podeli na konačno mnogo delova, od kojih se svaki razmatra posebno.

Primer. Dokažite da kvadrat prirodnog broja ne može da se završava cifrom 2.

Poslednja cifra kvadrata zavisi samo od poslednje cifre broja. Zato delimo prirodne brojeve na 10 delova prema poslednjoj cifri i proveravamo svaki deo:

$n$ se završava na	0	1	2	3	4
$n^2$ se završava na	0	1	4	9	6
$n$ se završava na	5	6	7	8	9
$n^2$ se završava na	5	6	9	4	1

U redovima za $n^2$ nema cifre 2, čime je zadatak rešen.

Princip matematičke indukcije

Kada je skup slučajeva beskonačan i ne može se podeliti na konačno mnogo delova, koriste se druge metode. Jedna od njih je metod matematičke indukcije. On se zasniva na jednoj od aksioma prirodnih brojeva koje je formulisao italijanski matematičar Đuzepe Peano (1889. godine). Zato je matematička indukcija, uprkos svom nazivu, deduktivni metod.

Aksioma indukcije. Ako skup $M$ prirodnih brojeva sadrži broj 1 i zajedno sa svakim brojem $k$ sadrži i sledeći broj ${k+1}$, onda $M$ sadrži sve prirodne brojeve.

U dokazima se ona koristi u sledećem obliku.

Princip matematičke indukcije. Neka je $T(n)$ tvrđenje o prirodnom broju $n$. Ako je $T(1)$ tačno i za svako prirodno $k$ iz tačnosti $T(k)$ sledi tačnost ${T(k+1)}$, onda je $T(n)$ tačno za svako prirodno $n$.

Zaista, neka je $M$ skup prirodnih brojeva za koje je $T(n)$ tačno. Po pretpostavci ${1\in M}$, i ako ${k\in M}$, onda ${k+1\in M}$. Po aksiomi indukcije $M$ sadrži sve prirodne brojeve, tj. $T(n)$ je tačno za svako prirodno $n$.

Zato dokaz indukcijom ima tri etape:

Baza: proveravamo da je tvrđenje tačno za ${n=1}$.
Induktivni korak: pretpostavljamo da je ono tačno za neko ${n=k}$ (induktivna pretpostavka) i dokazujemo da je tačno i za ${n=k+1}$.
Zaključak: po principu matematičke indukcije tvrđenje je tačno za svako prirodno $n$. Ono je tačno za ${n=1}$, dakle i za ${n=2}$, zatim i za ${n=3}$ itd.

Potrebni su i baza i korak. Neka je $T(n)$ tvrđenje „broj ${n^2+n}$ je neparan“. Korak je tačan: ako je ${k^2+k}$ neparan, onda je i ${(k+1)^2+(k+1)}={(k^2+k)+2(k+1)}$ neparan. Baza, međutim, nije tačna (${1^2+1=2}$) i zapravo je ${n^2+n=n(n+1)}$ paran za svako $n$.

Primeri

Primer 1. Dokažite da je

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

Baza. Za ${n=1}$ leva strana je ${S_1=1\cdot 2\cdot 3=6}$, a desna je ${\frac{1\cdot 2\cdot 3\cdot 4}{4}=6}$.

Korak. Pretpostavimo da je formula tačna za ${n=k}$, tj. ${S_k}={\frac{k(k+1)(k+2)(k+3)}{4}}$. Tada je

${S_{k+1}}={S_k}+{(k+1)(k+2)(k+3)}={\frac{k(k+1)(k+2)(k+3)}{4}}+{(k+1)(k+2)(k+3)}={\frac{(k+1)(k+2)(k+3)(k+4)}{4}}$,

jer je ${\frac{k}{4}+1=\frac{k+4}{4}}$. To je formula za ${n=k+1}$.

Zaključak. Formula je tačna za ${n=1}$ i iz njene tačnosti za ${n=k}$ sledi njena tačnost za ${n=k+1}$. Po principu matematičke indukcije ona je tačna za svako prirodno $n$.

Primer 2. Dokažite da je za svako prirodno $n$ broj ${11^{n+2}+12^{2n+1}}$ deljiv sa 133.

Baza. Za ${n=1}$: ${11^3+12^3}={1331+1728}={3059}={133\cdot 23}$.

Korak. Neka je ${11^{k+2}+12^{2k+1}=133p}$, gde je $p$ ceo broj. Pošto je ${144=11+133}$,

${11^{k+3}+12^{2k+3}}={11\cdot 11^{k+2}}+{144\cdot 12^{2k+1}}={11\left(11^{k+2}+12^{2k+1}\right)}+{133\cdot 12^{2k+1}}={133\left(11p+12^{2k+1}\right)}$.

Zaključak. Izraz je deljiv sa 133 za ${n=1}$, i ako je deljiv za ${n=k}$, deljiv je i za ${n=k+1}$. Prema tome, on je deljiv sa 133 za svako prirodno $n$.

Primer 3. Dokažite da skup ${M_n=\{a_1,a_2,\dots,a_n\}}$ ima $2^n$ podskupova.

Baza. Za ${n=1}$ skup ${M_1=\{a_1\}}$ ima dva podskupa: prazan skup i sam $M_1$. Njihov broj je ${2^1}$.

Korak. Pretpostavimo da ${M_k=\{a_1,\dots,a_k\}}$ ima $2^k$ podskupova i posmatrajmo ${M_{k+1}}={\{a_1,\dots,a_k,a_{k+1}\}}$. Podskupovi skupa $M_{k+1}$ koji ne sadrže $a_{k+1}$ su tačno podskupovi skupa $M_k$, tj. ima ih $2^k$. Podskupovi koji sadrže $a_{k+1}$ dobijaju se kada svakom podskupu skupa $M_k$ dodamo $a_{k+1}$, pa i njih ima $2^k$. Ukupno ${2^k+2^k=2\cdot 2^k=2^{k+1}}$.

Zaključak. Po principu matematičke indukcije $M_n$ ima $2^n$ podskupova za svako prirodno $n$.

Indukcija koja počinje od ${n=m}$

U primenama se često koristi i sledeća formulacija principa.

Neka je $m$ prirodan broj. Ako je tvrđenje $T(m)$ tačno i za svako ${k\ge m}$ iz tačnosti $T(k)$ sledi tačnost ${T(k+1)}$, onda je $T(n)$ tačno za svako prirodno ${n\ge m}$.

Ovde je baza provera tvrđenja za ${n=m}$.

Primer 4. Dokažite da je ${2^n\gt 2n+1}$ za svako prirodno ${n\ge 3}$.

Baza. Za ${n=3}$: ${2^3=8\gt 7=2\cdot 3+1}$. (Za ${n=2}$ nejednakost nije tačna: ${2^2=4\lt 5}$.)

Korak. Neka je ${2^k\gt 2k+1}$ za neko ${k\ge 3}$. Dokazaćemo da je ${2^{k+1}\gt 2(k+1)+1}$. Osim induktivne pretpostavke koristimo i ${2^k\gt 2}$:

${2^{k+1}}={2^k+2^k}\gt{(2k+1)+2}={2(k+1)+1}$.

Zaključak. Po principu matematičke indukcije (poslednja formulacija) ${2^n\gt 2n+1}$ za svako prirodno ${n\ge 3}$.

Hipoteza i dokaz

U istraživanjima često prvo treba otkriti zakonitost, izreći tvrđenje o njoj i tek onda ga dokazati za svako prirodno $n$. Tada redom primenjujemo nepotpunu indukciju, da bismo iz posebnih slučajeva postavili hipotezu, i matematičku indukciju, da bismo je dokazali. Etape su tri:

ogled i posmatranje;
postavljanje hipoteze;
dokazivanje hipoteze.

Primer 5. Nađite zbir prvih $n$ neparnih brojeva.

Zadatak traži kraću formulu za zbir ${S_n}={1+3+5+\dots}+{(2n-1)}$ od neposrednog sabiranja.

Prva etapa. Računamo $S_n$ za nekoliko uzastopnih vrednosti $n$: ${S_1=1}$, ${S_2=1+3=4}$, ${S_3=1+3+5=9}$, ${S_4=1+3+5+7=16}$ itd.:

$n$	1	2	3	4	5	6
$S_n$	1	4	9	16	25	36

Tražimo pravilo po kome se svaki broj iz drugog reda dobija od broja iznad njega. Primećujemo da je ${S_1=1^2}$, ${S_2=2^2}$, ${S_3=3^2}$, ${S_4=4^2}$, ${S_5=5^2}$ i ${S_6=6^2}$.

Druga etapa. Pravilo važi za ${n=1,2,\dots,6}$ i prirodno je pretpostaviti da važi za svako $n$:

${1+3+5+\dots}+{(2n-1)}={n^2}$.

Otkrivanje takve hipoteze zavisi od naše sposobnosti da posmatramo, naslućujemo i proveravamo naslućeno, od iskustva sa sličnim zadacima i od analogija sa već poznatim zadacima.

Treća etapa. Hipotezu dokazujemo matematičkom indukcijom. Za ${n=1}$ ona je tačna: ${S_1=1=1^2}$. Neka je ${S_k=k^2}$. Tada je

${S_{k+1}}={S_k+(2k+1)}={k^2+2k+1}={(k+1)^2}$.

Po principu matematičke indukcije ${S_n=n^2}$ za svako prirodno $n$, tj. hipoteza je tačna.

Ovde smo namerno podelili rešenje na tri etape da bi se jasno video njegov tok. U praksi etape prirodno prelaze jedna u drugu.

Zadaci

U zadacima 1–6 dokažite da je tvrđenje tačno za svako prirodno $n$.

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

Baza: ${\frac{1}{1\cdot 3}=\frac{1}{3}=\frac{1}{2\cdot 1+1}}$.

Korak: ${\frac{k}{2k+1}}+{\frac{1}{(2k+1)(2k+3)}}={\frac{2k^2+3k+1}{(2k+1)(2k+3)}}={\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}}={\frac{k+1}{2k+3}}$.

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

Baza: ${\frac{1}{1\cdot 4}=\frac{1}{4}=\frac{1}{3\cdot 1+1}}$.

Korak: ${\frac{k}{3k+1}}+{\frac{1}{(3k+1)(3k+4)}}={\frac{3k^2+4k+1}{(3k+1)(3k+4)}}={\frac{(3k+1)(k+1)}{(3k+1)(3k+4)}}={\frac{k+1}{3k+4}}$.

3. ${\frac{1}{a(a+1)}}+{\frac{1}{(a+1)(a+2)}}+{\dots+\frac{1}{(a+n-1)(a+n)}}={\frac{n}{a(a+n)}}$, gde je ${a\gt 0}$

Baza: za ${n=1}$ obe strane su jednake ${\frac{1}{a(a+1)}}$.

Korak: ${\frac{k}{a(a+k)}}+{\frac{1}{(a+k)(a+k+1)}}={\frac{k(a+k+1)+a}{a(a+k)(a+k+1)}}={\frac{(a+k)(k+1)}{a(a+k)(a+k+1)}}={\frac{k+1}{a(a+k+1)}}$, jer je ${ka+k^2+k+a}={(a+k)(k+1)}$.

4. ${2^{3n}-7n-1}$ je deljivo sa 49

${2^{3n}=8^n}$. Baza: ${8-7-1=0}$ je deljivo sa 49.

Korak: ${8^{k+1}-7(k+1)-1}={8\left(8^k-7k-1\right)+49k}$. Oba sabirka su deljiva sa 49.

5. ${2^{2n}+15n-1}$ je deljivo sa 9

${2^{2n}=4^n}$. Baza: ${4+15-1=18=9\cdot 2}$.

Korak: ${4^{k+1}+15(k+1)-1}={4\left(4^k+15k-1\right)}-{9(5k-2)}$. Oba člana su deljiva sa 9.

6. ${2^{n+2}\cdot 3^n+5n-4}$ je deljivo sa 25

Neka je ${A_n=2^{n+2}\cdot 3^n+5n-4}$. Baza: ${A_1=8\cdot 3+5-4=25}$.

Korak: ${A_{k+1}}={6\cdot 2^{k+2}\cdot 3^k+5k+1}={6A_k-25(k-1)}$, a $6A_k$ i ${25(k-1)}$ su deljivi sa 25.

U zadacima 7–10 nađite zbir. Izračunajte ga za nekoliko vrednosti $n$, postavite hipotezu i dokažite je indukcijom.

7. ${1+2+3+\dots+n}$

${\frac{n(n+1)}{2}}$. Korak: ${\frac{k(k+1)}{2}+(k+1)}={\frac{(k+1)(k+2)}{2}}$.

8. ${2+4+6+\dots+2n}$

${n(n+1)}$. Korak: ${k(k+1)+2(k+1)}={(k+1)(k+2)}$.

9. ${1\cdot 2+2\cdot 3+3\cdot 4}+{\dots+n(n+1)}$

${\frac{n(n+1)(n+2)}{3}}$. Korak: ${\frac{k(k+1)(k+2)}{3}}+{(k+1)(k+2)}={\frac{(k+1)(k+2)(k+3)}{3}}$.

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

Zbirovi su ${\frac{1}{2}}$, ${\frac{2}{3}}$, ${\frac{3}{4}}$, …, pa je hipoteza ${\frac{n}{n+1}}$. Korak: ${\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}}={\frac{k^2+2k+1}{(k+1)(k+2)}}={\frac{k+1}{k+2}}$.

Pogledajte i: Aritmetička progresija · Geometrijska progresija · Deljivost