Matemaattinen induktio | erityinen tapa todistaa matemaattinen totuus

Matemaattinen induktio on erityinen tapa todistaa matemaattinen totuus. Sen avulla voidaan todistaa, että jokin on totta kaikille luonnollisille luvuille (tai kaikille positiivisille luvuille jostain pisteestä alkaen). Ideana on, että jos:

Jokin on totta ensimmäisessä tapauksessa (perustapaus);
Aina kun sama asia on totta jossakin tapauksessa, se on totta myös seuraavassa tapauksessa (induktiivinen tapaus),

sitten

Sama pätee kaikkiin induktiotapauksiin.

Matematiikan varovaisessa kielenkäytössä induktiotodistus etenee usein seuraavasti:

Todistetaan, että todistus tehdään induktiolla n {\displaystyle n} . ( n {\displaystyle n} on induktiomuuttuja.)
Osoita, että väite on tosi, kun n {\displaystyle n} on 1.
Oletetaan, että väite on tosi mille tahansa luonnolliselle luvulle n {\displaystyle n} . (Tätä kutsutaan induktiovaiheeksi.)

Osoita sitten, että väite on tosi seuraavalle luvulle n + 1 {\displaystyle n+1} . $n+1$

Koska se on totta luvulle 1, se on totta luvulle 1+1 (=2, induktiovaiheessa), sitten se on totta luvulle 2+1 (=3), sitten se on totta luvulle 3+1 (=4) ja niin edelleen.

Esimerkkejä induktiotodistuksesta

n ensimmäisen luonnollisen luvun summa

Osoita, että kaikille luonnollisille luvuille 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)$

Todiste:

Ensinnäkin lausuma voidaan kirjoittaa seuraavasti:

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)$ (kaikille luonnollisille luvuille n)

Induktiolla n:n suhteen,

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

joten tämä on totta.

Seuraavaksi oletetaan, että jollekin n=n₀ väite on tosi. Toisin sanoen:

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

Sitten kun n=n₀ +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$

voidaan kirjoittaa uudelleen seuraavasti

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

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

Näin ollen todistus on täydellinen induktiolla.

Monikulmion sisäkulmien summa.

Matemaattinen induktio ilmoitetaan usein lähtöarvona 0 (eikä 1). Itse asiassa se toimii yhtä hyvin erilaisilla lähtöarvoilla. Seuraavassa on esimerkki, kun alkuarvo on 3: "n {\displaystyle n} -sivuisen monikulmion sisäkulmien summa on ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ astetta."

Lähtöarvo on 3, ja kolmion sisäkulmat ovat ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ astetta. Oletetaan, että n {\displaystyle n} -sivuisen monikulmion sisäkulmat ovat ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ astetta. Lisätään kolmio, joka tekee kuviosta n + 1 {\displaystyle n+1} monikulmion. $n+1$ -sivuinen monikulmio, jolloin kulmien lukumäärä kasvaa 180 asteella ( 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$ astetta. Koska sekä perustapaus että induktiivinen tapaus on käsitelty, todistus on nyt valmis.

On olemassa monia matemaattisia kohteita, joiden todistaminen matemaattisella induktiolla toimii. Tekninen termi on hyvin järjestetty joukko.

Induktiivinen määritelmä

Sama ajatus voi toimia sekä objektien joukon määrittelyssä että objektien joukkoa koskevien väitteiden todistamisessa.

Voimme esimerkiksi määritellä n {\displaystyle n} th asteen serkun seuraavasti:

1 {\displaystyle 1} $1$ serkku on vanhemman sisaruksen lapsi.
N + 1 {\displaystyle n+1} $n+1$ st-asteen serkku on vanhemman n {\displaystyle n} th-asteen serkun lapsi.

Luonnollisten lukujen aritmetiikkaa varten on olemassa joukko aksioomia, jotka perustuvat matemaattiseen induktioon. Tätä kutsutaan nimellä "Peanon aksioomat". Määrittelemättömät symbolit ovat | ja =. Aksioomat ovat seuraavat.

| on luonnollinen luku.
Jos n {\displaystyle n} on luonnollinen luku, niin n | {\displaystyle n|} $n|$ on luonnollinen luku.
Jos n | = m | {\displaystyle n|=m|} $n|=m|$ niin n = m {\displaystyle n=m} . $n=m$

Tämän jälkeen voidaan määritellä yhteenlasku- ja kertolaskuoperaatiot ja niin edelleen matemaattisen induktion avulla. Esimerkiksi:

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

Aiheeseen liittyvät sivut

Matemaattinen todiste
Todistus ristiriidan kautta

Kysymyksiä ja vastauksia

K: Mitä on matemaattinen induktio?

V: Matemaattinen induktio on erityinen tapa todistaa matemaattinen totuus, jonka avulla voidaan todistaa, että jokin on totta kaikille luonnollisille luvuille tai positiivisille luvuille tietystä pisteestä alkaen.

K: Miten induktiotodistus etenee?

V: Induktiotodistus etenee tyypillisesti siten, että todetaan, että todistus tehdään yli n, osoitetaan, että väite on tosi, kun n on 1, oletetaan, että väite on tosi mille tahansa luonnolliselle luvulle n, ja sitten osoitetaan, että se on tosi seuraavalle luvulle (n+1).

Kysymys: Mitä tarkoittaa olettaa jotain induktiivisessa vaiheessa?

V: Jonkin asian olettaminen induktiivisessa vaiheessa tarkoittaa sen hyväksymistä todeksi ilman todisteita tai todisteita. Se toimii lähtökohtana jatkotutkimukselle.

K: Millaisia lukuja käytetään matemaattisessa induktiossa?

V: Matemaattisessa induktiossa käytetään tyypillisesti luonnollisia lukuja tai positiivisia lukuja tietystä kohdasta alkaen.

K: Miten osoitetaan, että jokin on totta seuraavalle luvulle (n+1)?

V: Osoittaaksesi, että jokin on totta seuraavalle luvulle (n+1), sinun on ensin osoitettava, että se on totta, kun n=1, ja sen jälkeen osoitettava induktiovaiheessa tekemäsi oletuksen avulla, että se on totta myös luvulle n+1.