Title: Induktiotodistukset

Feedback shared by this category's questions, if right: Vastauksesi on oikein.
Feedback shared by this category's questions, if partly right: Vastauksesi on osittain oikein.
Feedback shared by this category's questions, if wrong: Vastauksesi on väärin.

Q: Seuraavissa tehtävissä jatketaan induktiotodistukseen tutustumista.

Tarkastellaan väitettä, jonka mukaan

\( \sum \limits_{i=0}^n (4i+1) = (n+1)(2n+1)+1 \)

kaikilla luonnollisilla luvuilla \( n \). Kaverisi on laatinut väitteelle seuraavanlaisen todistuksen.

Todistus ei kuitenkaan ole oikein, vaan siinä on yksi virhe. Etsi virhe ja vedä sen kohdalle oikea selitys.
- Zone 1 | Vaihe puuttuu.
Also offered: Induktio-oletusta on käytetty väärin.; Sulut on avattu väärin.; Todistus on oikein.; Summan indeksöinti on väärin.
Feedback: Todistuksessa ei tarkisteta, päteekö väite luvulla nolla.

Q: Tarkastellaan väitettä, jonka mukaan \( 2n^2+1 > 3n \) kaikilla positiivisilla kokonaisluvuilla \(n\). Kaverisi on laatinut väitteelle seuraavanlaisen todistuksen.

Todistus ei kuitenkaan ole oikein. Etsi virheelliset kohdat ja vedä selitykset näihin paikkoihin.
- Zone 1 | Vaihe puuttuu.
Also offered: Sulut on avattu väärin.; Induktio-oletusta on käytetty väärin.; Epäyhtälö ei päde.

Q: Induktiotodistus on keskeinen työväline matematiikassa. Sen avulla voidaan todistaa väitteitä kaikille luonnollisille luvuille. Hieman muunnellen sitä voi käyttää lukujen sijaan todistamaan asioita myös esimerkiksi kaikille propositiolauseille (logiikassa) tai vaikkapa kaikille binääripuille (tietojenkäsittelytieteessä). Aloitetaan induktiotodistuksen harjoittelu summakaavan todistamisella. Voit ottaa mallia esimerkistä 4.1.2.

Tarkoituksena on todistaa induktiolla, että

\( \sum \limits_{i=0}^{n} (3i-2) = \frac{(n+1)(3n-4)}{2} \)

kaikilla luonnollisilla luvuilla \(n\).

Laita induktiotodistuksen vaiheet oikeaan järjestykseen.

[...] Tässä vaiheessa näytettäisiin, että väite pätee luvulla \(n=0\).

[...] Tässä vaiheessa tehtäisiin ensin [...], eli oletettaisiin väitteen pätevän jollain \(k \in \mathbb{N}\). Tämän jälkeen näytettäisiin, että tällöin väite pätee myös luvulla \(k+1\).

[...] Lopuksi todettaisiin, että edellisen perusteella väite pätee [...] nojalla kaikilla \(n \in \mathbb{N}\).
A: Alkuaskel:; Induktioaskel:; induktio-oletus; Johtopäätös:; induktioperiaatteen
Feedback: Alkuaskel: Tässä vaiheessa näytettäisiin, että väite pätee luvulla \(n=0\). Induktioaskel: Tässä vaiheessa tehtäisiin ensin induktio-oletus, eli oletettaisiin väitteen pätevän jollain \(k \in \mathbb{N}\). Tämän jälkeen näytettäisiin, että tällöin väite pätee myös luvulla \(k+1\). Johtopäätös: Lopuksi todettaisiin, että edellisen perusteella väite pätee induktioperiaatteen nojalla kaikilla \(n \in \mathbb{N}\).

Q: Fibonaccin lukujono määritellään rekursiivisesti asettamalla \( F_0=0, F_1=1 \) ja lisäksi

\( F_n = F_{n-1} + F_{n-2} \) kaikilla luonnollisilla luvuilla \( n \geq 2 \).

Tarkastellaan väitettä

\( \sum \limits_{i=0}^n F_i = F_{k+2} - 1. \)

Täydennä väitteen induktiotodistuksen rakenne.

Todistus

Alkuaskel: Tarkistetaan, että väite pätee luvulla [...].
A: 0
Gap 1 offers: 0; 1; 2

Q: Tässä tehtävässä mahdolliset lausekkeet tulee kirjoittaa aina yhteen. Tarkista, ettet lisää välilyöntejä vastauksiisi.

Osoitetaan induktiolla, että kaikilla \(n \in \mathbb{N}\) pätee

\(\sum \limits_{i=0}^n i(i+1) = \frac{n(n+1)(n+2)}{3}\).

Todistus. [...]: Tarkastellaan, päteekö väite luvulla [...]. Tällöin yhtälön vasemmalle puolelle saadaan luku [...]

ja oikealle puolelle luku [...]. Siis väite [...] luvulla [...].

[...]: Tehdään induktio-oletus, että väite pätee [...]. Pyritään osoittamaan, että tällöin väite pätee myös luvulla [...]. Nyt

 \(\sum \limits_{i=0}^{n+1} i(i+1)\)

 \(\overset{(1)}= \sum \limits_{i=0}^n i(i+1) +\) [...]

 \(\overset{(2)}= \frac{n(n+1)(n+2)}{3} +\) [...]

 \(\overset{(3)}= \frac{n(n+1)(n+2)}{3} + \frac{3(n+1)(n+2)}{3}\)

 \(\overset{(4)}= \) [...] / 3,

missä induktio-oletusta käytettiin välivaiheessa [...].

Siis väite pätee luvulla [...]. Induktioperiaatteen nojalla

\(\sum \limits_{i=0}^n i(i+1) = \frac{n(n+1)(n+2)}{3}\) kaikilla \(n \in \mathbb{N}\).
A: Alkuaskel; 0; 0; 0; pätee; 0; Induktioaskel; jollakin luonnollisella luvulla n; n+1; (n+1)(n+2); (n+1)(n+2); (n+1)(n+2)(n+3); 2; n+1
Gap 1 offers: Alkuaskel; Induktioaskel; Induktio-oletus
Gap 5 offers: pätee; ei päde
Gap 7 offers: Alkuaskel; Induktioaskel; Induktio-oletus
Gap 8 offers: luvulla 0; luvulla 1; kaikilla luonnollisilla luvuilla n; jollakin luonnollisella luvulla n
Gap 10 offers: n(n+1); (n+1)(n+2); n(n+1)(n+2)
Gap 11 offers: n(n+1); (n+1)(n+2); n(n+1)(n+2)
Gap 12 offers: (n+1)(n+2)(n+3); n(n+1)(n+2); (n+1)(n+2); 3(n+1)(n+2)
Gap 13 offers: 1; 2; 3; 4
Feedback: Todistus. Alkuaskel: Tarkastellaan, päteekö väite luvulla \(0\). Tällöin yhtälön vasemmalle puolelle saadaan \(0\) ja oikealle puolelle \(0\). Siis väite pätee luvulla \(0\). Induktioaskel: Tehdään induktio-oletus, että väite pätee jollakin \(n \in \mathbb{N}\). Pyritään osoittamaan, että tällöin väite pätee myös luvulla \(n+1\). Nyt \(\sum \limits_{i=0}^{n+1} i(i+1)\) \(\overset{(1)}= \sum \limits_{i=0}^n i(i+1) + (n+1)(n+2)\) \(\overset{(2)}= \frac{n(n+1)(n+2)}{3} + (n+1)(n+2)\) \(\overset{(3)}= \frac{n(n+1)(n+2)}{3} + \frac{3(n+1)(n+2)}{3}\) \(\overset{(4)}= \frac{(n+1)(n+2)(n+3)}{3}\) eli väite pätee luvulla \(n+1\). Olemme osoittaneet, että \(\sum \limits_{i=0}^n i(i+1) = \frac{n(n+1)(n+2)}{3}\) kaikilla \(n \in \mathbb{N}\). Induktio-oletusta käytettiin välivaiheessa 2.

Q: Valitse paras ilmaus siten, että todistus on looginen ja noudattaa hyvää matemaattista kirjoitustapaa.

Osoitetaan, että \(6^n - 1\) on jaollinen luvulla \(5\) kaikilla \(n \in \mathbb{N}\).

Todistus. Alkuaskel: [...] väite pätee luvulla \(0\). Nyt \(6^0 - 1 = 1 - 1 = 0\) ja luku \(0\) on jaollinen [...]. Siis väite pätee luvulla \(0\).

Induktioaskel: [...] väite pätee [...] \(k \in \mathbb{N}\). [...] väite pätee myös [...] luvulla \(k+1\).

Induktio-oletuksen nojalla \(6^k - 1\) on jaollinen luvulla \(5\), mikä [...] mukaan tarkoittaa sitä, että \(6^k - 1 = 5m\) [...] \(m \in \mathbb{Z}\). Tämä on [...] sen kanssa, että \(6^k = 5m + 1\). Nähdään, että

\(6^{k+1} - 1 = 6 \cdot 6^k - 1\)

                  \( = 6(5m + 1) - 1\)

                  \( = 30m + 5\)

                  \( =  5(6m + 1)\),

[...] \(6m + 1 \in \mathbb{Z}\). Määritelmän nojalla \(6^{k+1} - 1\) on jaollinen luvulla \(5\), joten väite pätee myös [...] luvulla \(k+1\).

Olemme osoittaneet, että väite pätee [...] \(n \in \mathbb{N}\).
A: Osoitetaan, että; luvulla 5; Oletetaan, että; jollakin; Osoitetaan, että; (tyhjä); määritelmän; jollakin; yhtäpitävää; missä; (tyhjä); kaikilla
Gap 1 offers: Oletetaan, että; Osoitetaan, että; Tiedetään, että; (tyhjä)
Gap 2 offers: 5:llä; luvulla 5; (tyhjä)
Gap 3 offers: Oletetaan, että; Osoitetaan, että; Tiedetään, että; (tyhjä)
Gap 4 offers: jollakin; kaikilla; kun; jos
Gap 5 offers: Oletetaan, että; Osoitetaan, että; Tiedetään, että; (tyhjä)
Gap 6 offers: jollakin; mielivaltaisella; (tyhjä)
Gap 7 offers: määritelmän; oletuksen; alkuaskeleen
Gap 8 offers: jollakin; kaikilla; kun; jos
Gap 9 offers: yhtäsuurta; yhtäpitävää; sama
Gap 10 offers: kun; jos; missä
Gap 11 offers: jollakin; mielivaltaisella; (tyhjä)
Gap 12 offers: jollakin; kaikilla; tietyillä
Feedback: Todistus. Alkuaskel: Osoitetaan, että väite pätee luvulla \(0\). Nyt \(6^0 - 1 = 1 - 1 = 0\) ja luku \(0\) on jaollinen luvulla \(5\). Siis väite pätee luvulla \(0\). Induktioaskel: Oletetaan, että väite pätee jollakin \(k \in \mathbb{N}\). Osoitetaan, että väite pätee myös luvulla \(k+1\). Induktio-oletuksen nojalla \(6^k - 1\) on jaollinen luvulla \(5\), mikä määritelmän mukaan tarkoittaa sitä, että \(6^k - 1 = 5m\) jollakin \(m \in \mathbb{Z}\). Tämä on yhtäpitävää sen kanssa, että \(6^k = 5m + 1\). Nähdään, että \(6^{k+1} - 1 = 6 \cdot 6^k - 1\) \( = 6(5m + 1) - 1\) \( = 30m + 5\) \( = 5(6m + 1)\), missä \(6m + 1 \in \mathbb{Z}\). Määritelmän nojalla \(6^{k+1} - 1\) on jaollinen luvulla \(5\), joten väite pätee myös luvulla \(k+1\). Olemme osoittaneet, että väite pätee kaikilla \(n \in \mathbb{N}\).

Todistetaan induktiolla Bernoullin epäyhtälö: jos \(x \in \mathbb{R}\) ja \(x > -1\), niin \((1+x)^n \geq 1+nx\) kaikilla \(n \in \mathbb{N}\).

Alkuaskel: Tutkitaan, päteekö väite luvulla . Epäyhtälön vasen puoli saa tällöin arvon ja oikea puoli arvon . Siis väite pitää paikkansa luvulla .

Induktioaskel: Tehdään induktio-oletus, että väite pätee jollakin luonnollisella luvulla \(n\). Halutaan näyttää, että väite pätee tällöin myös luvulla . Nyt

\((1+x)^{n+1} \overset{(1)}= \) \((1+x)\)
\( \overset{(2)}\geq (\) \() (1+x)\)
\( \overset{(3)}= 1+(n+1)x+nx^2\)
\( \overset{(4)}\geq \) ,

missä viimeinen epäyhtälö seuraa siitä, että \(nx^2 \geq 0\) kaikilla \(x \in \mathbb{R}\).

Siten väite pätee myös luvulla . Induktio-oletusta käytettiin välivaiheessa (anna vastaukseksi numero 1–4) .

Induktioperiaatteen nojalla väite pätee nyt kaikilla luonnollisilla luvuilla.
Feedback: Alkuaskel: Tutkitaan, päteekö väite luvulla \(0\). Epäyhtälön vasen puoli saa tällöin arvon \(0\) ja oikea puoli arvon \(1\). Siis väite pitää paikkansa luvulla \(0\). Induktioaskel: Tehdään induktio-oletus, että väite pätee jollakin luonnollisella luvulla \(n\). Halutaan näyttää, että väite pätee tällöin myös luvulla \(n+1\). Nyt \((1+x)^{n+1} \overset{(1)}= (1+x)^n (1+x)\) \( \overset{(2)}\geq (1+nx) (1+x)\) \( \overset{(3)}= 1+(n+1)x+nx^2\) \( \overset{(4)}\geq 1+(n+1)x\), missä viimeinen epäyhtälö seuraa siitä, että \(nx^2 \geq 0\). Siten väite pätee myös luvulla \(n+1\). Induktio-oletusta käytettiin välivaiheessa 2. Induktioperiaatteen nojalla väite pätee nyt kaikilla luonnollisilla luvuilla.

Tämä tehtävä on jatkoa binääripuita käsittelevälle tehtävälle.

Tarkastellaan sukupuuta, joka muodostuu seuraavasti:
1. Jos henkilön vanhemmat eivät ole tiedossa, henkilöstä ei lähde lainkaan nuolia.
2. Jos henkilön vanhemmat ovat tiedossa, henkilöstä vedetään nuoli kumpaankin vanhempaan.
3. Tämä sääntö toistetaan jokaisen henkilön kohdalla uudestaan.

[Image]

Osoita induktiolla, että \(n \geq 1\) sukupolvea näyttävä puu koostuu enintään \(2^n - 1\) ihmisestä.

Todistus. Alkuaskel. Osoitetaan, että väite pätee luvulla \(n = \) . Kun sukupolvia on , niin ihmisiä sukupuussa on . Toisaalta \(2^n - 1 = \) , joten väite pitää paikkansa.

Induktioaskel. Tehdään induktio-oletus, että väite pätee jollakin positiivisella kokonaisluvulla \(k\). Osoitetaan, että tällöin väite pätee myös luvulla . Induktio-oletuksen nojalla \(k\) nuorimmassa sukupolvessa on yhteensä enintään ihmistä. Vanhimmassa eli :nnessä sukupolvessa taas on enintään (Vihje: voit katsoa apua täydellisiä binääripuita koskevasta tehtävästä) ihmistä. Kaiken kaikkiaan sukupuussa on siis enintään ihmistä, mikä haluttiin osoittaa.

Induktioperiaatteen nojalla väite pätee nyt kaikilla positiivisilla kokonaisluvuilla \(n\).
Feedback: Todistus muutamalla lisähuomiolla varustettuna: Todistus. Alkuaskel: Osoitetaan, että väite pätee luvulla \(1\). Kun sukupolvia on \(1\), on ihmisiä sukupuussa \(1\) (tehtävän kuvaa "luetaan" alhaalta ylöspäin; kyseessä on siis puun juurisolmu). Toisaalta \(2^1 - 1 = 2 - 1 = 1\), joten väite pätee luvulla \(1\). Induktioaskel: Tehdään induktio-oletus, että väite pätee jollakin positiivisella kokonaisluvulla \(k\). Osoitetaan, että tällöin väite pätee myös luvulla \(k + 1\). Induktio-oletuksen nojalla puun \(k\) nuorimmassa sukupolvessa on yhteensä enintään \(2^k - 1\) ihmistä. Vanhimmassa eli \(k + 1\):nnessä sukupolvessa ihmisiä on enintään \(2^k\). (Jos puun kaikki tasot ovat täynnä eli jokaisella henkilöllä on molemmat vanhemmat tiedossa, niin alhaalta laskettuna \(m\):nnellä tasolla on \(2^{m-1}\) solmua.) Yhteensä ihmisiä \(k + 1\) polvessa on siis enintään \(2^k - 1 + 2^k = 2 \cdot 2^k - 1 = 2^{k+1} - 1\), mikä haluttiin osoittaa. Induktioperiaatteen nojalla väite pätee kaikilla positiivisilla kokonaisluvuilla \(n\).

Fibonaccin lukujono määritellään rekursiivisesti asettamalla \( F_0=0, F_1=1 \) ja lisäksi

\( F_n = F_{n-1} + F_{n-2} \) kaikilla luonnollisilla luvuilla \( n \geq 2 \).

Tarkastellaan väitettä

\( F_n \geq \left( \frac{3}{2} \right)^{n-2}\)

kaikilla \(n \in \mathbb{N} \setminus \{0\}\).

Täydennä väitteen induktiotodistuksen rakenne.

Todistus

Alkuaskel: Tarkistetaan, että väite pätee luvuilla \(n=\) ja \(n=\) .

Näissä tilanteissa epäyhtälön oikealle puolelle saadaan  ja  (anna pienempi luku ensin). Koska \(F_1=F_2=\) , alkuaskel pätee.

Induktioaskel: Tehdään induktio-oletus. Oletetaan, että \(k \geq 1\) on luonnollinen luku ja väite pätee kaikilla \(j \in \{1, \ldots, k\}\).

Tarkastellaan väitettä luvulla  . Alkuaskeleessa tarkistettiin jo väite luvuilla  ja  , joten voidaan olettaa tässä, että \(k \geq 2\). Tällöin \(k+1 \geq 3\), joten voidaan käyttää Fibonaccin lukujonon määritelmän rekursiokaavaa. Lisäksi \(k \geq 2\) ja \(k-1 \geq 1\), joten induktio-oletusta voidaan soveltaa lukuihin \(k\) ja \(k-1\).

Induktio-oletuksen mukaan pätee siis \(F_k \geq\) ja \(F_{k-1} \geq\) , joten saadaan

\( F_{k+1} \overset{(1)} = F_k + F_{k-1} \overset{(2)} \geq \left( \frac{3}{2} \right)^{k-2} + \left( \frac{3}{2} \right)^{k-3} \overset{(3)} \geq \left( \frac{3}{2} +1 \right) \cdot \left( \frac{3}{2} \right)^{k-3} \overset{(4)} \geq \frac{5}{2} \cdot \left( \frac{3}{2} \right)^{k-3}. \)

Rekursioyhtälöä käytettiin kohdassa (numero 1-4)  ja induktio-oletusta kohdassa (numero 1-4)  .

Toisaalta \( \left( \frac{3}{2} \right)^{(k+1)-2}= \) \(\cdot \left(\frac{3}{2} \right)^{k-3}\).

Yllä olevista laskuista nähdään, että väite pätee myös luvulla .

Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).
Feedback: Todistus Alkuaskel: Tarkistetaan, että väite pätee luvuilla \(n=1\) ja \(n=2\). Näissä tilanteissa epäyhtälön oikealle puolelle saadaan \(\frac{2}{3}\) ja \(1\). Koska \(F_1=F_2=1\), väite alkuaskel pätee. Induktioaskel: Tehdään induktio-oletus. Oletetaan, että \(k \geq 1\) on luonnollinen luku ja väite pätee kaikilla \(j \in \{1, \ldots, k\}\). Tarkastellaan väitettä luvulla \(k+1\). Alkuaskeleessa tarkistettiin jo väite luvuilla \(1\) ja \(2\), joten voidaan olettaa tässä, että \(k \geq 2\). Tällöin \(k+1 \geq 3\), joten voidaan käyttää Fibonaccin lukujonon määritelmän rekursiokaavaa. Lisäksi \(k \geq 2\) ja \(k-1 \geq 1\), joten induktio-oletusta voidaan soveltaa lukuihin \(k\) ja \(k-1\). Induktio-oletuksen mukaan pätee siis \(F_k \geq \left( \frac{3}{2} \right)^{k-2}\) ja \(F_{k-1} \geq \left( \frac{3}{2} \right)^{k-3}\), joten saadaan \( F_{k+1} \overset{(1)} = F_k + F_{k-1} \overset{(2)} \geq \left( \frac{3}{2} \right)^{k-2} + \left( \frac{3}{2} \right)^{k-3} \overset{(3)} \geq \left( \frac{3}{2} +1 \right) \cdot \left( \frac{3}{2} \right)^{k-3} \overset{(4)} \geq \frac{5}{2} \cdot \left( \frac{3}{2} \right)^{k-3}. \) Rekursioyhtälöä käytettiin kohdassa \(1\) ja induktio-oletusta kohdassa \(2\). Toisaalta \( \left( \frac{3}{2} \right)^{(k+1)-2}=\frac{9}{4}\cdot \left(\frac{3}{2} \right)^{k-3}\). Yllä olevista laskuista nähdään, että väite pätee myös luvulla \(k+1\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).

Pyritään osoittamaan, että \(2^n > 4n\) kaikilla luonnollisilla luvuilla \(n > 4\).

Täydennä väitteen induktiotodistus.

Todistus

Alkuaskel: Tarkistetaan, että väite pätee luvulla \(n= \) . Tällöin \(2^n= \)  ja \(4n= \)  , joten väite pätee, kun \(n= \) .

Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollakin \(k \in \mathbb{N}\), \(k > 4\). Tällöin \(2^k > 4k\).

Näytetään sitten, että väite pätee tällöin myös luvulla  . Nyt

\( 2^{k+1} \overset{(1)} = 2 \cdot 2^k \overset{(2)} = 2^k+2^k \overset{(3)} > 4k+4k \overset{(4)} > 4k+4 \overset{(5)} = 4(k+1). \)

Kohdassa (numero 1-5)  käytettiin induktio-oletusta ja kohdassa (numero 1-5)  tietoa \(k>4\).

Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N}\), \(n > 4\).
Feedback: Todistus Alkuaskel: Tarkistetaan, että väite pätee luvulla \(n=5\). Tällöin \(2^n=32\) ja \(4n=20\), joten väite pätee, kun \(n=5\). Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollain \(k \in \mathbb{N}\), \(k > 4\). Tällöin \(2^k > 4k\). Näytetään sitten, että väite pätee tällöin myös luvulla \(k+1\). Nyt \( 2^{k+1} \overset{(1)} = 2 \cdot 2^k \overset{(2)} = 2^k+2^k \overset{(3)} > 4k+4k \overset{(4)} > 4k+4 \overset{(5)} = 4(k+1). \) Kohdassa \(3\) käytettiin induktio-oletusta ja kohdassa \(4\) tietoa \(k>4\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N}\), \(n > 4\).

Jatketaan induktion harjoittelua. Induktio soveltuu hyvin tilanteisiin, joissa esimerkiksi lukujono on määritelty rekursiivisesti. Rekursiivinen määrittely tarkoittaa sitä, että jonon jäsenet riippuvat edellisistä jonkin annetun säännön mukaisesti. Tällöin induktioaskeleessa voi yleensä hyödyntää suoraan kyseistä riippuvuussääntöä.

Fibonaccin lukujono määritellään rekursiivisesti asettamalla \( F_0=0, F_1=1 \) ja lisäksi

\( F_n = F_{n-1} + F_{n-2} \) kaikilla luonnollisilla luvuilla \( n \geq 2 \).

Tarkastellaan väitettä

\( \sum \limits_{i=0}^n F_i = F_{n+2} - 1\)

kaikilla \(n \in \mathbb{N} \).

Täydennä väitteen induktiotodistuksen rakenne.

Todistus

Alkuaskel: Tarkistetaan, että väite pätee luvulla \(n= \) . Yhtälön vasemmalle puolelle saadaan  ja oikealle puolelle  .

Vasen ja oikea puoli ovat yhtä suuret, joten yhtälö pätee, kun \(n=\) .

Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollakin \(k \in \mathbb{N}\). Tällöin

\( \sum \limits_{i=0}^k F_i = F_{k+2} - 1. \)

Näytetään sitten, että väite pätee tällöin myös luvulla  . Rekursioyhtälön ja induktio-oletuksen perusteella saadaan

\( \sum \limits_{i=0}^{k+1} F_i \overset{(1)} = \sum \limits_{i=0}^{k} F_i + F_{k+1}\overset{(2)} = F_{k+2}-1+F_{k+1} \overset{(3)} = F_{k+1}+F_{k+2}-1 \overset{(4)}= F_{k+3}-1.\)

Kohdassa  (vastaukseksi numero 1-4 ilman sulkumerkkejä) käytettiin rekursioyhtälöä ja kohdassa (vastaukseksi numero 1-4 ilman sulkumerkkejä) induktio-oletusta.

Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N}\).
Feedback: Todistus Alkuaskel: Tarkistetaan, että väite pätee luvulla \(n=0\). Yhtälön vasemmalle puolelle saadaan \(0\) ja oikealle puolelle \(0\). Vasen ja oikea puoli ovat yhtä suuret, joten yhtälö pätee, kun \(n=0\). Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollain \(k \in \mathbb{N}\). Tällöin \( \sum \limits_{i=0}^k F_i = F_{k+2} - 1. \) Näytetään sitten, että väite pätee tällöin myös luvulla \(k+1\). Rekursioyhtälön ja induktio-oletuksen perusteella saadaan \( \sum \limits_{i=0}^{k+1} F_i \overset{(1)} = \sum \limits_{i=0}^{k} F_i + F_{k+1}\overset{(2)} = F_{k+2}-1+F_{k+1} \overset{(3)} = F_{k+1}+F_{k+2}-1 \overset{(4)}= F_{k+3}-1.\) Kohdassa \(4\) käytettiin rekursioyhtälöä ja kohdassa \(2\) induktio-oletusta. Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N}\).

Induktiotodistusta voi käyttää lukemattomien erilaisten väitteiden todistamiseen. Seuraavassa tehtävässä todistettava väite ei ole kaava tai epäyhtälö, mutta induktiota voi silti käyttää todistuksessa tavalliseen tapaan. Vähän samantapainen tilanne on kurssimateriaalin esimerkissä 4.1.6. Tutustu tuohon esimerkkiin ja matki sen rakennetta. Kiinnitä erityisesti huomiota siihen, miten induktioaskelta lähdetään todistamaan sen jälkeen, kun on tehty induktio-oletus.

Tarkastellaan kolmea pylvästä \(A, B\) ja \(C\), joihin voidaan pinota erikokoisia renkaita. Lähtötilanteessa renkaat ovat pylväässä \(A\) suuruusjärjestyksessä suurin alla, pienin päällä kuten alla olevassa kuvassa.

[Image]

Renkaat on siirrettävä pylvääseen \(C\). Vain yhtä rengasta saa siirtää kerrallaan ja missään vaiheessa ei pienempi rengas saa olla suuremman alla. Pyrkimyksenä on osoittaa induktiolla, että kaikilla positiivisilla kokonaisluvuilla \(n\) pätee

"jos renkaiden lukumäärä on \(n\), niin \(2^n-1\) siirtoa riittää niiden siirtämiseen".

Täydennä induktiotodistuksen vaiheet.

Todistus

Alkuaskel: Osoitetaan, että väite pätee pienimmällä renkaiden määrällä, siis kun \(n= \) . Tällöin \(2^n-1= \)  . Toisaalta jos renkaita on  , niin siirtoja tarvitaan  , jotta kaikki renkaat saadaan siirrettyä pylväästä \(A\) pylvääseen \(C\). Siis alkuaskel pätee.

Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollakin \(k \in \mathbb{N} \setminus \{0\}\), eli jos renkaiden lukumäärä on \(k\), niin  siirtoa riittää niiden siirtämiseen. Näytetään, että tällöin väite pätee myös siinä tapauksessa, kun renkaiden lukumäärä on  .

Tarkastellaan väitettä luvun  tapauksessa: kuvitellaan  renkaasta muodostunut torni pylvääseen \(A\). Jaetaan tarkastelu kolmeen vaiheeseen:

1. Ensin induktio-oletuksen mukaisesti tornin ylimmät  rengasta voidaan siirtää pylvääseen \(B\) käyttämällä korkeintaan  siirtoa.

2. Seuraavaksi siirretään suurin rengas, jonka päällä ei enää ole renkaita, pylvääseen \(C\).

3. Lopuksi käyttämällä uudestaan induktio-oletusta saadaan \(k\) renkaasta muodostuva torni siirrettyä pylväästä \(B\) pylvääseen \(C\) suurimman renkaan päälle  siirrolla.

Yhteensä siirtoja tehtiin siis .

Näin ollen väite pätee myös luvulla .

Johtopäätös: Alku- ja induktioaskeleesta seuraa  induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).
Feedback: Todistus Alkuaskel: Osoitetaan, että väite pätee pienimmällä renkaiden määrällä, siis kun \(n= 1\). Tällöin \(2^n-1= 1\) . Toisaalta jos renkaita on \(1\), niin siirtoja tarvitaan \(1\), jotta kaikki renkaat saadaan siirrettyä pylväästä \(A\) pylvääseen \(C\). SIis alkuaskel pätee. Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollain \(k \in \mathbb{N} \setminus \{0\}\), eli jos renkaiden lukumäärä on \(k\), niin \(2^k-1\) siirtoa riittää niiden siirtämiseen. Näytetään, että tällöin väite pätee myös siinä tapauksessa, kun renkaiden lukumäärä on \(k+1\). Tarkastellaan väitettä luvun \(k+1\) tapauksessa: kuvitellaan \(k+1\) renkaasta muodostunut torni pylvääseen \(A\). Jaetaan tarkastelu kolmeen vaiheeseen: 1. Ensin induktio-oletuksen mukaisesti tornin ylimmät \(k\) rengasta voidaan siirtää pylvääseen \(B\) käyttämällä korkeintaan \(2^k-1\) siirtoa. 2. Seuraavaksi siirretään suurin rengas, jonka päällä ei enää ole renkaita, pylvääseen \(C\). 3. Lopuksi käyttämällä uudestaan induktio-oletusta saadaan \(k\) renkaasta muodostuva torni siirrettyä pylväästä \(B\) pylvääseen \(C\) suurimman renkaan päälle \(2^k-1\) siirrolla. Yhteensä siirtoja tehtiin siis \(2^{k+1}-1\). Näin ollen väite pätee myös luvulla \(k+1\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).

Osoitetaan, että \( [value]^n+[value]n-1 \) on jaollinen luvulla \([value]\) kaikilla luonnollisilla luvuilla \(n \geq 1\).
Täydennä väitteen induktiotodistus.

Todistus

Alkuaskel: Näytetään, että väite pätee luvulla \(n=\) . Tällöin \( [value]^n+[value]n-1 =\) , joka on jaollinen luvulla \([value]\). Näin ollen väite pätee luvulla \(n=\) .

Induktioaskel: Tehdään induktio-oletus, eli oletetaan, että väite pätee  \(k \in \mathbb{N} \setminus \{0\}\). Induktio-oletuksen nojalla siis \( [value]^k+[value]k-1 = [value]q\) jollain \(q \in \mathbb{Z}\). Tämä on yhtäpitävää sen kanssa, että \( [value]^k= \) .

Näytetään, että väite pätee tällöin myös luvulla \(k+1\). Nyt

\([value]^{k+1}+[value](k+1)-1 = [value] \cdot [value]^k + [value]k+[value]-1 \)

                                          \(\overset{\text{IO}}= [value](\) \()+ [value]k+[value]\)

                                          \(= [value]q+[value]-[value]k+[value]k+[value] \)

                                          \(= [value]q-[value]k+[value] \)

                                          \(= [value](\) \(),\)

missä \(\in \mathbb{Z}\). Kohdassa \(\text{IO}\) käytettiin induktio-oletusta.

Näin ollen luku \([value]^{k+1}+[value](k+1)-1\) on jaollinen luvulla \([value]\), joten väite pätee myös luvulla \(k+1\).

Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee  \(n \in \mathbb{N} \setminus \{0\}\).
Feedback: Todistus Alkuaskel: Näytetään, että väite pätee luvulla \(n=1\). Tällöin \( [value]^n+[value]n-1 =[value]\), joka on jaollinen luvulla \([value]\). Näin ollen väite pätee luvulla \(n=1\). Induktioaskel: Tehdään induktio-oletus, eli oletetaan, että väite pätee jollain \(k \in \mathbb{N} \setminus \{0\}\). Induktio-oletuksen nojalla siis \( [value]^k+[value]k-1 = [value]q\) jollain \(q \in \mathbb{Z}\). Tämä on yhtäpitävää sen kanssa, että \( [value]^k=[value]q+1-[value]k \). Näytetään, että väite pätee tällöin myös luvulla \(k+1\). Nyt \([value]^{k+1}+[value](k+1)-1 = [value] \cdot [value]^k + [value]k+[value]-1 \) \(\overset{\text{IO}}= [value]([value]q+1-[value]k)+ [value]k+[value]\) \(= [value]q+[value]-[value]k+[value]k+[value] \) \(= [value]q-[value]k+[value] \) \(= [value]([value]q-[value]k+[value]),\) missä \([value]q-[value]k+[value] \in \mathbb{Z}\). Kohdassa \(\text{IO}\) käytettiin induktio-oletusta. Näin ollen luku \([value]^{k+1}+[value](k+1)-1\) on jaollinen luvulla \([value]\), joten väite pätee myös luvulla \(k+1\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\}\).

Oletetaan, että \(z \in \mathbb{C}\). Pyritään todistamaan, että \(|z^n|=|z|^n\) kaikilla luonnollisilla luvuilla \(n \geq 1\). Todistuksessa käytetään apuna kurssimateriaalin tulosta 7.4.6.

Täydennä väitteen induktiotodistus.

Todistus

Alkuaskel: Väite pätee luvulla \(n= \) , koska \(|z^1|=|z| =|z|^1\).

Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee \(k \in \mathbb{N} \setminus \{0\} \). Tällöin \(|z^k|=|z|^k\).

Näytetään, että väite pätee tällöin myös luvulla :

\( |z^{k+1}|\overset{(1)}=|z^k \cdot z|\overset{(2)}= |z^k| \cdot |z| \overset{(3)}=|z|^k \cdot |z | \overset{(4)}=|z|^{k+1}.\)

Kohdassa (numero 1-4)  käytettiin lausetta 7.4.6 ja kohdassa (numero 1-4)  induktio-oletusta.

Väite pätee siis myös luvulla .

Johtopäätös: Alku- ja induktioaskeleesta seuraa  nojalla, että väite pätee  \(n \in \mathbb{N} \setminus \{0\} \).

Määritä vielä lopuksi kompleksiluvun \(z=([value]+[value]i)^{[value]}\) itseisarvo.

\(|z|= \)
Feedback: Todistus Alkuaskel: Väite pätee luvulla \(n=1\), koska \(|z^1|= |z| =|z|^1\). Induktioaskel: Tehdään induktio-oletus. Oletetaan siis, että väite pätee jollain \(k \in \mathbb{N} \setminus \{0\} \). Tällöin \(|z^k|=|z|^k\). Näytetään, että väite pätee tällöin myös luvulla \(k+1\): \( |z^{k+1}|\overset{(1)}=|z^k \cdot z|\overset{(2)}=|z^k| \cdot |z| \overset{(3)}=|z|^k \cdot |z | \overset{(4)}=|z|^{k+1}.\) Kohdassa \(2\) käytettiin lausetta 7.4.6 ja kohdassa \(3\) induktio-oletusta. Väite pätee siis myös luvulla \(k+1\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \). Käyttämällä äsken osoitettua tulosta saadaan \(|z|= |([value]+[value]i)^{[value]}|= |[value]+[value]i|^{[value]}=(\sqrt{[value]^2+[value]^2})^{[value]}=[value]\).

Jänne tarkoittaa ympyrän kahden pisteen välistä janaa. Jos jänne kulkee ympyrän keskipisteen kautta, sitä sanotaan ympyrän halkaisijaksi. Oletetaan, että \(n \in \mathbb{N}\) ja \(n \geq 1\). Tarkastellaan tilannetta, jossa ympyrälle piirretään \(n\) jännettä.

Olkoon \(P(n)\) väite

"\(n\) jänteen rajaamat alueet voidaan värittää kahdella värillä niin, että mitkään kaksi vierekkäistä aluetta eivät ole samanväriset".

Alla olevassa on havainnoillistettu väitteitä \(P(1)\) ja \(P(2)\). Piirrä lisää kuvia ja tutki, päteekö väite \(P(n)\) mielestäsi pienillä luvun \(n\) arvoilla.

[Image]

Täydennä väitteen induktiotodistus.

Todistus

Alkuaskel: Näytetään, että väite pätee luvulla \(n=\) . Kun jänteitä piirretään  , ympyrä jakautuu alueisiin, joiden lukumäärä on . Kun alueita on  , ne voidaan värittää eri värillä. Tällöin kaikki syntyneet alueet ovat eri värisiä, joten väite pätee luvulla \(n=\) .

Induktioaskel: Tehdään induktio-oletus. Oletetaan, että väite pätee jollakin \(k \in \mathbb{N} \setminus \{0\} \). Näytetään, että väite pätee tällöin myös siinä tapauksessa, että jänteiden lukumäärä on  .

Tarkastellaan jotakin ympyrää, johon on piirretty  jännettä. Poistetaan jänteistä yksi. Induktio-oletuksen perusteella näin syntyneet alueet voidaan värittää kahdella värillä siten, että mitkään vierekkäiset alueet eivät ole samanväriset. Palautetaan sitten poistettu jänne kuvaan. Tarkastellaan palautetun jänteen yhdellä puolella olevia alueita ja vaihdetaan näiden jokaisen väri.

Näytetään täsmällisesti, että kaikki vierekkäiset alueet ovat nyt eri väriset. Tarkastellaan joitakin vierekkäisiä alueita \(A\) ja \(B\). On kaksi tapausta.

1. Jos \(A\) ja \(B\) ovat palautetun jänteen samalla puolella, ne olivat alun perin eri värisiä. Tällöin joko niiden väriä ei vaihdettu tai molempien väri vaihdettiin. Ne ovat siis edelleen eri värisiä.

2. Jos \(A\) ja \(B\) ovat palautetun jänteen eri puolilla, niin ne olivat alun perin osa samaa aluetta ja siis samanväriset. Kun jänne palautettiin, vain toisella puolella olevan alueen väri vaihdettiin, joten lopulta alueet \(A\) ja \(B\) ovat eri väriset.

Näin ollen väritys voidaan tehdä vaaditulla tavalla, joten väite pätee myös luvulla  .

Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).
Feedback: Todistus Alkuaskel: Näytetään, että väite pätee luvulla \(n=1\). Kun jänteitä piirretään \(1\), ympyrä jakautuu alueisiin, joiden lukumäärä on \(2\). Kun alueita on \(2\), ne voidaan värittää eri värillä. Tällöin kaikki syntyneet alueet ovat eri värisiä, joten väite pätee luvulla \(n=1\). Induktioaskel: Tehdään induktio-oletus. Oletetaan, että väite pätee jollain \(k \in \mathbb{N} \setminus \{0\} \). Näytetään, että väite pätee tällöin myös siinä tapauksessa, että jänteiden lukumäärä on \(k+1\). Tarkastellaan jotakin ympyrää, johon on piirretty \(k+1\) jännettä. Poistetaan jänteistä yksi. Induktio-oletuksen perusteella näin syntyneet alueet voidaan värittää kahdella värillä siten, että mitkään vierekkäiset alueet eivät ole samanväriset. Palautetaan sitten poistettu jänne kuvaan. Tarkastellaan palautetun jänteen yhdellä puolella olevia alueita ja vaihdetaan näiden jokaisen väri. Näytetään täsmällisesti, että kaikki vierekkäiset alueet ovat nyt eri väriset. Tarkastellaan joitakin vierekkäisiä alueita \(A\) ja \(B\). On kaksi tapausta. 1. Jos \(A\) ja \(B\) ovat palautetun jänteen samalla puolella, ne olivat alun perin eri värisiä. Tällöin joko niiden väriä ei vaihdettu tai molempien väri vaihdettiin. Ne ovat siis edelleen eri värisiä. 2. Jos \(A\) ja \(B\) ovat palautetun jänteen eri puolilla, niin ne olivat alun perin osa samaa aluetta ja siis samanväriset. Kun jänne palautettiin, vain toisella puolella olevan alueen väri vaihdettiin, joten lopulta alueet \(A\) ja \(B\) ovat eri väriset. Näin ollen väritys voidaan tehdä vaaditulla tavalla, joten väite pätee myös luvulla \(k+1\). Johtopäätös: Alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että väite pätee kaikilla \(n \in \mathbb{N} \setminus \{0\} \).

Tarkastellaan oheisen kuvan kaltaista täydellistä binääripuuta, jonka jokaisella solmulla on täsmälleen kaksi tai nolla lapsisolmua ja jonka kaikki lehdet (solmut ilman lapsia) ovat yhtä kaukana juurisolmusta. Juurisolmun syvyys on \(0\), sen lasten syvyys \(1\), jne.

[Image]

Osoitetaan induktiolla, että jos täydellisen binääripuun lehtien syvyys on \(n\), niin lehtien lukumäärä on \(2^n\).

Todistus. Alkuaskel. Tarkastellaan väitettä luvulla \(n = \) . Binääripuussa on tällöin lehti/lehteä. Toisaalta \(2^n = \) , joten väite pätee luvulla \(n = \).

Induktioaskel. Tehdään induktio-oletus, että väite pätee jollakin \(\in \mathbb{N}\). Halutaan osoittaa, että tällöin väite pätee myös luvulla \(k+1\).

Induktio-oletuksen nojalla puussa, jonka lehtien syvyys on , on lehteä. Lisäämällä näille solmuille lasta kullekin, saadaan täydellinen binääripuu, jonka lehtien syvyys on \(k+1\). Nyt syvyydessä \(k+1\) on yhteensä \(2 \cdot 2^k = \) lehteä. Siis väite pätee luvulla .

Induktioperiaatteen nojalla väite pätee kaikilla \(n \in \mathbb{N}\).
Feedback: Todistus. Alkuaskel. Tarkastellaan väitettä luvulla \(n = 0\). Binääripuussa on tällöin \(1\) solmu (juurisolmu), ja siten täsmälleen \(1\) lehti. Toisaalta \(2^n = 2^0 = 1\), joten väite pätee luvulla \(0\). Induktioaskel. Tehdään induktio-oletus, että väite pätee jollakin \(k \in \mathbb{N}\). Halutaan osoittaa, että tällöin väite pätee myös luvulla \(k+1\). Induktio-oletuksen nojalla puussa, jonka lehtien syvyys on \(k\), on \(2^k\) lehteä. Lisäämällä näille solmuille \(2\) lasta kullekin, saadaan täydellinen binääripuu, jonka lehtien syvyys on \(k+1\). Nyt syvyydessä \(k+1\) on yhteensä \(2 \cdot 2^k = 2^{k+1}\) lehteä. Siis väite pätee luvulla \(k+1\). Induktioperiaatteen nojalla väite pätee kaikilla \(n \in \mathbb{N}\).