Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Popolna indukcija

Avtor: E-um (vsebinsko), Skupina NAUK (tehnično)

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega socialnega sklada Evropske unije in Ministrstva za šolstvo in šport. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Inštitut za matematiko, fiziko in mehaniko in podjetje Hruška d.o.o.

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

Uporabljeni viri

E-um

www.e-um.si

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega socialnega sklada Evropske unije in Ministrstva za šolstvo in šport. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Inštitut za matematiko, fiziko in mehaniko in podjetje Hruška d.o.o.

Uvod

V tem poglavju bomo spoznali postopek za dokazovanje trditev, ki veljajo za vsa naravna števila.

Zgodovinska zanimivost

Popolna ali matematična indukcija je orodje za dokazovanje trditev oz. lastnosti v množici naravnih števil. Temelji na dveh korakih.

Preverimo, ali dana trditev oz. lastnost velja za prvo naravno število, torej za $n=1$ .

Preverimo implikacijo: če trditev velja za neko naravno število $n$ , potem velja tudi za naslednika $n+1$ .

Z veljavnostjo obeh korakov je trditev dokazana za vsa naravna števila.

Z matematično indukcijo dokazujemo lastnosti oz. trditve, katerih razultati so nam vnaprej znani.

Zgodovinska zanimivost

Pierre de Format, francoski matematik (1601–1665), je domneval, da so vsa števila oblike $2^{2^n}+1$ praštevila za vse $n \in \mathbb{N}$ .

Preveril je za $n=1, 2, 3 \dots$ in res dobil sama praštevila, zato je sklepal, da to drži za vsa naravna števila.

Žal pa trditev že za $n=5$ ne velja, saj je $2^{2^5}+1=4294967297 = 641 \cdot 6700417$ sestavljeno število.

Nauk zgodbe:

Iz dejstva, da neka lastnost velja za prvih nekaj naravnih števil, še ne moremo sklepati, da ta lastnost velja za vsa naravna števila.

Za veljavnost trditve, da ta velja za vsa naravna števila, je potreben dokaz.

Primer dokaza s popolno indukcijo

Dokažimo veljavnost obrazca za vsoto prvih n naravnih števil

To enakost bomo dokazali še malo drugače, in sicer z metodo, ki nam omogoča dokazovanje mnogih trditev v zvezi z naravnimi števili. Ta metoda se imenuje popolna ali matematična indukcija.

Radi bi torej dokazali, da je $1+2+\dots+n=\frac{n}{2}(n+1)$ .

Pa začnimo sistematično po korakih.

Najprej dokažimo, da enakost velja v primeru, ko je $n=1$ oz. želimo dokazati, da enakost velja za prvo naravno število.
Poglejmo levo stran: 1
Vstavimo $n=1$ še v desno stran: $\frac{1}{2}(1+1)=\frac{1}{2}\cdot2=1$
Trditev velja za prvo naravno število, saj je leva stran enaka desni.
Prevzemimo, da lastnost velja za število $n$ , in dokažimo, da velja tudi za naslednje naravno število $n+1$ oz. namesto $n$ vstavimo v enačbo $n+1$ . Dokazujemo implikacijo $n \Rightarrow n+1$ .
Ob predpostavki: $1+2+\dots+n=\frac{n}{2}(n+1)$ bi radi dokazali, da velja tudi:
1. Poglejmo najprej levo stran:
2. Izračunajmo še desno strano stran:
  $\frac{n+1}{2}(n+1+1)=\frac{(n+1)(n+2)}{2}$

Leva stran je enaka desni, torej je drugi korak izpolnjen.

Izpolnjena sta oba koraka, kar pomeni, da enakost $1+2+ \dots +n =$ velja za vsak $n \in \mathbb{N}$ .

Vsota prvih $n \in \mathbb{N}$

Zanima nas vsota prvih $n$ naravnih števil, torej $1+2+\dots+n$

Vidimo, da je zaporedje aritmetično $a_1=1$ in $d=1=1$ ter $a_n=n$ .

Vsota prvih $n$ členov aritmetičnega zaporedja je $S_n=\frac{n}{2}(a_n+a_1)$ .

Zato je $1+2+\dots+n=\frac{n}{2}(n+1)$

Poskusi sam

S popolno indukcijo dokaži, da velja $2\cdot3+2\cdot5+2\cdot7+\dots2\cdot(2n+1)=n\cdot(2n+4)$ za vsak $n \in \mathbb{N}$ .

Poglej postopek

Preizkusi se!

Preveri pravilnost spodnje trditve.

$2^2+4^2+6^2\dots+(2n)^2=\frac{n(n+1)^2}{2}$

Pravilno

Napačno

Odlično! Rezultat je viden že po prvem koraku.

Naprej

To pa ne bo držalo! Rezultat je viden že po prvem koraku.

Preverimo, ali trditev velja za prvi člen, vstavimo n=1.
1. Preverimo levo stran: $2\cdot3=6$ .
2. Izračunamo še desno stran: $1(2\cdot1+4)=6$
  Ugotovimo, da trditev za $n=1$ velja.

Prevzemimo, da velja $2\cdot3+2\cdot5+2\cdot7+\dots2\cdot(2n+1)=n\cdot(2n+4)$ in dokažimo, da velja tudi za naslednika. Vstavimo namesto $n$ $n+1$ in dokazujemo, da velja: $2\cdot3+2\cdot5+2\cdot7+\dots2\cdot(2n+1)+ 2(2(n+1)+1)=(n+1)(2(n+1)+4)$ .
1. Leva stran:
  
  Odpravimo oklepaje, poenostavimo in razstavimo: $2n^2+4n+4n+6=2(n^2+4n+3)=2(n+1)(n+3).$
2. Poglejmo še desno stran: $(n+1)(2(n+1)+4)=(n+1)2(n+1+2)=2(n+1)(n+3).$ .

Leva stran je enaka desni, kar pomeni, da implikacija velja.

Dokazali smo zgornjo trditev.

Domine

Ugotovitev

Včasih določena trditev ne velja za vsa naravna števila, pač pa za vsa naravna števila od nekje naprej, recimo $n \geq 3$ . V tem primeru se postopek izvedbe matematične indukcije smiselno spremeni: v prvi fazi trditev dokažemo za $n=3$ , drugi korak pa ostane nespremenjen.

Ilustrirajmo povedano s primerom domin.

Domine

Zlagamo domine s številkami $1, 2, 3 \dots$ Denimo, da to storimo tako, da vemo dvoje:

če bomo podrli eno domino, bo podrta tudi naslednja,
podremo prvo domino.

Kaj lahko sklepamo? Da bodo padle vse!

Kaj pa če vemo:

če bomo podrli eno domino, bo podrta tudi naslednja,
podremo tretjo domino.

V tem primeru pa lahko sklepamo, da bodo podrte vse od tretje dalje ...

Domine

Število diagonal v konveksnem $n$ -kotniku

Pravilno si odgovoril na vsa vprašanja.
S tem si dokazal, da je v konveksnem $n$ -kotniku število diagonal $\frac{n(n-3)}{2}$ za $n>3$ .

Naprej

Na nekaj vprašanj si odgovoril narobe.

Dokaz z indukcijo

Oglejmo si dokaz te iste trditve, tokrat še z matematično indukcijo.

Pred tem pa si nazorno poglejmo primer petkotnika, ki mu dodamo eno oglišče.

Dokaz:

Število diagonal v konveksnem $n$ -kotniku je $\frac{n(n-3)}{2}$ , za $n>3$ .

Dokažimo, da to velja za vse konveksne $n$ -kotnike, $n>3$ z uporabo matematične indukcije:

Prvi konveksni $n$ -kotnik je trikotnik, torej vstavimo $n=3$ .
Št. diagonal v trikotniku: $\frac{3(3-3)}{2}=0$ , trditev velja za trikotnik.
Prevzemimo, da ima konveksni $n$ -kotnik $\frac{n(n-3)}{2}$ diagonal in dokažimo implikacijo, da iz $n \Rightarrow n+1$ , da ima torej konveksni $(n+1)$ -kotnik $\frac{(n+1)(n+1-3)}{2}$ diagonal.
Poglejmo konveksni $(n+1)$ -kotnik, če mu odvzamemo eno oglišče. Dobimo konveksni $n$ -kotnik, ki ima $\frac{n(n-3)}{2}$ diagonal. Natančno proučimo, kaj je s številom diagonal v odvzetem oglišču $(n+1)$ -kotnika.
Številu vseh diagonal $n$ -kotnika dodamo še št. diagonal iz zadnjega $(n+1)$ oglišča: $(n+1)-3$ , prišteti pa moramo še eno diagonalo, ki nastane iz stranice v $n$ -kotniku, kar se lepo vidi na zgornji sliki v primeru za petkotnik (diagonala AE).
Torej: $\frac{n(n-3)}{2}+ ((n+1)-3)+1=\frac{n(n-3)}{2}+n-1=\frac{n(n-3)}{2} + \frac{2(n-1)}{2}=\frac{n^2-3n+2n-2}{2}=\frac{(n+1)(n-2)}{2}$

Dokazali smo drugi indukcijski korak.

Dokazana sta torej oba koraka matematične indukcije, zato trditev velja za vsa naravna števila .

Za lažje razumevanje dokaza si znova oglej primer petkotnika.

Primer petkotnika

Aplikacija RiŠ se ni mogla zagnati. Prosim preverite, ali imate v brskalniku namescen program Java 1.4.2 (ali novejsi) (Kliknite tu za namestitev Jave)

Riš datoteka

Deljivost

Poskusi se še v deljivosti.

Dokaži, da $6 \mid (7^n-1)$ za vsako naravno število n.

Dokaz

Matematična indukcija je sredstvo za dokazovanje trditev, povezanih z naravnimi števili.

Pri dokazovanju z indukcijo je treba prej poznati rezultat, ki ga želimo dokazati.

Dokler rezultata nekako ne pridobimo (v nekaterih primerih ga uganemo, včasih ga nekako izračunamo, lahko pa nam ga tudi kdo pove ...), si z indukcijo ne moremo pomagati.

Če pa rezultat poznamo, ga lahko pogosto dokažemo z indukcijo dokažemo.

Dokaz

Lotimo se matematične indukcije.

Najprej trditev dokažimo za $n=1$ . Dobimo: $6 \mid (7^1-1)$ .

Predpostavimo, da $6 \mid (7^n-1)$ , in dokažimo, da trditev velja tudi za $n+1$ . Dokazati želimo, da iz $6 \mid (7^n-1)$ sledi $6 \mid (7^{n+1}-1)$ .
Razpišimo potenco $7^{n+1}$ : $6 \mid (7\cdot7^n-1)$ ,
preoblikujmo do znanih stvari: $7\cdot7^n-1=7^n + 6\cdot7^n-1$ ,
združimo člene: $7^n + 6\cdot7^n-1=7^n-1 + 6\cdot7^n$ ,
Vemo: $6 \mid (7^n-1)$ . Očitno velja tudi $6 \mid 6^n$ . Zato $6$ deli tudi vsoto teh dveh števil, torej $6 \mid (7^{n+1}-1)$ .

Izvedli smo oba koraka matematične indukcije, zato trditev velja za vsako naravno število $n$ .

Dodatne naloge

1. naloga

Dokaži, da spodnje trditve veljajo za vsa naravna števila.

(Nalogo reši na papir.)

$2+4+6+\dots+2n=n(n+1)$

$1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}$

$1+2^{-1}+2^{-2}+\dots+2^{-n+1}=2-n^{1-n}$

$6\mid(n^3-n)$

V konveksnem $n$ -kotniku je vsota notranjih kotov $(n-2)\cdot 180°$

Dodatne naloge

2. naloga

Na osnovi začetnih nekaj vsot $S1$ , $S2$ , $\dots Sn$ ugani zapisano vsoto in dobljeno trditev dokaži.

(Dokaze trditev napiši na papir.)

a) $\frac{1}{1\cdot5}+\frac{1}{5\cdot9}+\frac{1}{9\cdot13}+\dots+\frac{1}{(4n-3)\cdot(4n+1)}$

Preveri vsoto

b)Primerjaj vsoti $1 + 2 + 3 + ... + n$ in $1^3 + 2^3 + ... + n^3$ . Oglej si vsoti za začetnih nekaj naravnih števil $n$ in ugani obrazec za drugo vsoto. Trditev potem dokaži s popolno indukcijo.

Preveri vsoto

Rešitev

$S_n=\frac{n}{4n+1}$

Rešitev

$S_n=\frac{n}{2}(n+1)$ in $S_n=(\frac{n}{2}(n+1))^2$

Popolna indukcija

Vaš brskalnik je zastarel

Pritisnite F11

Popolna indukcija

Avtor: E-um (vsebinsko), Skupina NAUK (tehnično)

Sodelujoče organizacije

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

Uporabljeni viri

Sodelujoče organizacije

Zgodovinska zanimivost

Nauk zgodbe:

Dokažimo veljavnost obrazca za vsoto prvih n naravnih števil

Vsota prvih n \in \mathbb{N}

Preizkusi se!

Ugotovitev

Domine

Dokaz:

Dokaz

1. naloga

2. naloga

Rešitev

Rešitev

Vsota prvih $n \in \mathbb{N}$