Matematična indukcija

Matematična indukcija je poseben način dokazovanja matematične resnice. Z njo lahko dokažemo, da nekaj velja za vsa naravna števila (vsa pozitivna cela števila). Ideja je, da

Nekaj velja za prvi primer
Enako velja za naslednji primer

nato

Enako velja za vse primere

V skrbnem jeziku matematike:

Navedite, da bo dokaz potekal z indukcijo nad n {\displaystyle n} . ( n {\displaystyle n} je indukcijska spremenljivka.)
Pokaži, da je izjava resnična, če je n {\displaystyle n} 1.
Predpostavimo, da je izjava resnična za vsako naravno število n {\displaystyle n} . (To imenujemo korak indukcije.)

Pokažite, da trditev velja tudi za naslednje število, n + 1 {\displaystyle n+1} $n+1$ .

Ker velja za 1, potem velja za 1+1 (=2, s korakom indukcije), potem velja za 2+1 (=3), potem velja za 3+1 (=4) in tako naprej.

Primer dokaza z indukcijo:

Dokažite, da za vsa naravna števila n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Dokaz:

Najprej lahko izjavo zapišemo: za vsa naravna števila n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$

Z indukcijo na n,

Najprej za n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

zato je to res.

Nato predpostavimo, da je za nekatere n=n0 izjava resnična. To pomeni, da:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

Potem za n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{{n_{0}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

se lahko prepiše

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Ker 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Zato je dokaz pravilen.

Podobni dokazi

Matematična indukcija je pogosto navedena z začetno vrednostjo 0 (in ne 1). Dejansko pa deluje enako dobro z različnimi začetnimi vrednostmi. Tukaj je primer, ko je začetna vrednost 3. Vsota notranjih kotov n {\displaystyle n}stranskega mnogokotnika je( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ stopinj.

Začetna začetna vrednost je 3, notranji koti trikotnika pa so ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ stopinj. Predpostavimo, da so notranji koti n {\displaystyle n}stranskega mnogokotnika( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ stopinj. Dodamo še trikotnik, zaradi katerega je lik sestavljen iz n + 1 {\displaystyle n+1} kotov. $n+1$ tem se število kotov poveča za 180 stopinj ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ stopinj. Dokazano.

Obstaja veliko matematičnih objektov, za katere je dokazovanje z matematično indukcijo uspešno. Tehnični izraz je dobro urejena množica.

Induktivna opredelitev

Ista zamisel se lahko uporablja tako za opredelitev kot tudi za dokazovanje.

Določite n {\displaystyle n}-stopenjski bratranec:

Bratranec 1 {\displaystyle 1} $1$ prve stopnje je otrok starševega sorojenca.
Bratranec n + 1 {\displaystyle n+1} $n+1$ prve stopnje je otrok bratranca n {\displaystyle n} tretje stopnje starša.

Za aritmetiko naravnih števil obstaja niz aksiomov, ki temelji na matematični indukciji. Imenuje se "Peanovi aksiomi". Nedoločena simbola sta | in =. Aksiomi so

| je naravno število
Če je n {\displaystyle n} naravno število, potem je n | {\displaystyle n|} $n|$ naravno število
Če n | = m | {\displaystyle n|=m|} $n|=m|$ , potem n = m {\displaystyle n=m} $n=m$

Nato lahko z matematično indukcijo opredelimo operacije seštevanja in množenja itd. Na primer:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Vprašanja in odgovori

V: Kaj je matematična indukcija?

O: Matematična indukcija je poseben način dokazovanja matematične resnice, s katerim lahko dokažemo, da nekaj velja za vsa naravna števila ali pozitivna števila od določene točke naprej.

V: Kako poteka dokaz z indukcijo?

O: Dokaz z indukcijo običajno poteka tako, da se navede, da bo dokaz izveden nad n, pokaže, da je izjava resnična, ko je n 1, predpostavi, da je izjava resnična za vsako naravno število n, in nato pokaže, da je resnična za naslednje število (n+1).

V: Kaj pomeni, če v induktivnem koraku nekaj predpostavljamo?

O: Domnevati nekaj v induktivnem koraku pomeni sprejeti nekaj kot resnično, ne da bi predložili dokaze ali potrditev. Služi kot izhodišče za nadaljnje raziskovanje.

V: Katere vrste števil se uporabljajo pri matematični indukciji?

O: Matematična indukcija običajno uporablja naravna števila ali pozitivna števila od določene točke naprej.

V: Kako dokažete, da je nekaj resnično za naslednje število (n+1)?

O: Če želite dokazati, da nekaj velja za naslednje število (n+1), morate najprej dokazati, da to velja za n=1, nato pa uporabiti predpostavko iz indukcije in dokazati, da to velja tudi za n+1.