Teljes indukció

A matematikai indukció a matematikai igazság bizonyításának egy speciális módja. Ezzel bizonyíthatjuk, hogy valami igaz az összes természetes számra (az összes pozitív egész számra). Az elképzelés az, hogy

Valami igaz az első esetre
Ugyanez mindig igaz a következő esetre is.

majd

Ugyanez igaz minden esetben.

A matematika óvatos nyelvén:

Állapítsa meg, hogy a bizonyítás n {\displaystyle n} fölött indukcióval történik. ( n {\displaystyle n} az indukciós változó.)
Mutassuk meg, hogy az állítás igaz, ha n {\displaystyle n} 1.
Tegyük fel, hogy az állítás igaz bármely n természetes számra {\displaystyle n} . (Ezt nevezzük indukciós lépésnek.)

Mutassuk meg, hogy az állítás igaz a következő számra, n + 1 {\displaystyle n+1} $n+1$ .

Mert igaz az 1-re, akkor igaz az 1+1-re (=2, az indukciós lépés alapján), akkor igaz a 2+1-re (=3), akkor igaz a 3+1-re (=4), és így tovább.

Példa az indukciós bizonyításra:

Bizonyítsuk be, hogy minden n természetes számra:

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)$

Bizonyíték:

Először is, az állítás felírható: minden n természetes szám eseté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)$

Indukcióval n-re,

Először is, n=1 esetén:

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)$ ,

tehát ez igaz.

Ezután tegyük fel, hogy bizonyos n=n0 esetén az állítás igaz. Vagyis:

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)$

Ezután n=n0+1:

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

átírható

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)$

Mivel 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)$

A bizonyítás tehát helyes.

Hasonló bizonyítékok

A matematikai indukciót gyakran 0 (és nem 1) kezdőértékkel adják meg. Valójában ugyanolyan jól működik különböző kezdőértékekkel is. Íme egy példa, amikor a kiindulási érték 3. Egy n {\displaystyle n} oldalú sokszög belső szögeinek összege ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ fok.

A kiindulási érték 3, és a háromszög belső szöge ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ fok. Tegyük fel, hogy egy n {\displaystyle n} oldalú sokszög belső szöge ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ fok. Adjunk hozzá egy háromszöget, amely az ábrát n + 1 {\displaystyle n+1} $n+1$ oldalú sokszöggé, és ez 180 fokkal növeli a szögek számát ( 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$ fokkal. Bizonyított.

Nagyon sok olyan matematikai objektum van, amelyre a matematikai indukcióval történő bizonyítás működik. A szakkifejezés a jól rendezett halmaz.

Induktív meghatározás

Ugyanez a gondolat működhet a meghatározás és a bizonyítás terén is.

Határozza meg az n {\displaystyle n} th fokú unokatestvért:

Az 1 {\displaystyle 1} $1$ elsőfokú unokatestvér a szülő testvérének gyermeke.
Az n + 1 {\displaystyle n+1} $n+1$ elsőfokú unokatestvér a szülő n {\displaystyle n} harmadikfokú unokatestvérének gyermeke.

A természetes számok aritmetikájához létezik egy axiómakészlet, amely a matematikai indukción alapul. Ezt "Peano axiómáinak" nevezik. A határozatlan szimbólumok a | és az =. Az axiómák a következők

| egy természetes szám
Ha n {\displaystyle n} egy természetes szám, akkor n | {\displaystyle n|} $n|$ egy természetes szám.
Ha n | = m | {\displaystyle n|=m|} $n|=m|$ akkor n = m {\displaystyle n=m} $n=m$

Ezután matematikai indukcióval meghatározhatjuk az összeadás és a szorzás stb. műveleteit. Például:

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

Kérdések és válaszok

K: Mi az a matematikai indukció?

V: A matematikai indukció a matematikai igazság bizonyításának egy speciális módja, amellyel bebizonyítható, hogy egy bizonyos ponttól kezdve minden természetes számra vagy pozitív számra igaz valami.

K: Hogyan zajlik az indukciós bizonyítás?

V: Az indukciós bizonyítás jellemzően úgy megy végbe, hogy kijelentjük, hogy a bizonyítás n számra fog történni, megmutatjuk, hogy az állítás igaz, amikor n 1, feltételezzük, hogy az állítás igaz bármely n természetes számra, majd megmutatjuk, hogy igaz a következő számra (n+1).

K: Mit jelent az induktív lépésben feltételezni valamit?

V: Induktív lépésben feltételezni valamit azt jelenti, hogy bizonyíték vagy bizonyítás nélkül igaznak fogadjuk el. Ez kiindulópontként szolgál a további vizsgálatokhoz.

K: Milyen számokat használnak a matematikai indukcióban?

V: A matematikai indukció egy bizonyos ponttól kezdve jellemzően természetes számokat vagy pozitív számokat használ.

K: Hogyan lehet megmutatni, hogy valami igaz a következő számra (n+1)?

V: Ahhoz, hogy megmutassuk, hogy valami igaz a következő számra (n+1), először be kell bizonyítanunk, hogy igaz, amikor n=1, majd az induktív lépésből származó feltételezésünket felhasználva meg kell mutatnunk, hogy az n+1-re is igaz.