\[\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bff}{\mathbf{f}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bi}{\mathbf{i}} \newcommand{\bj}{\mathbf{j}} \newcommand{\bk}{\mathbf{k}} \newcommand{\bN}{\mathbf{N}} \newcommand{\bn}{\mathbf{n}} \newcommand{\bo}{\mathbf{0}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bs}{\mathbf{s}} \newcommand{\bT}{\mathbf{T}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bzero}{\mathbf{0}} \newcommand{\nv}{\mathbf{0}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cT}{\mathcal{T}} \newcommand{\cU}{\mathcal{U}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cW}{\mathcal{W}} \newcommand{\cX}{\mathcal{X}} \newcommand{\cY}{\mathcal{Y}} \newcommand{\cZ}{\mathcal{Z}} \newcommand{\rA}{\mathrm{A}} \newcommand{\rB}{\mathrm{B}} \newcommand{\rC}{\mathrm{C}} \newcommand{\rD}{\mathrm{D}} \newcommand{\rE}{\mathrm{E}} \newcommand{\rF}{\mathrm{F}} \newcommand{\rG}{\mathrm{G}} \newcommand{\rH}{\mathrm{H}} \newcommand{\rI}{\mathrm{I}} \newcommand{\rJ}{\mathrm{J}} \newcommand{\rK}{\mathrm{K}} \newcommand{\rL}{\mathrm{L}} \newcommand{\rM}{\mathrm{M}} \newcommand{\rN}{\mathrm{N}} \newcommand{\rO}{\mathrm{O}} \newcommand{\rP}{\mathrm{P}} \newcommand{\rQ}{\mathrm{Q}} \newcommand{\rR}{\mathrm{R}} \newcommand{\rS}{\mathrm{S}} \newcommand{\rT}{\mathrm{T}} \newcommand{\rU}{\mathrm{U}} \newcommand{\rV}{\mathrm{V}} \newcommand{\rW}{\mathrm{W}} \newcommand{\rX}{\mathrm{X}} \newcommand{\rY}{\mathrm{Y}} \newcommand{\rZ}{\mathrm{Z}} \newcommand{\pv}{\overline} \newcommand{\iu}{\mathrm{i}} \newcommand{\ju}{\mathrm{j}} \newcommand{\im}{\mathrm{i}} \newcommand{\e}{\mathrm{e}} \newcommand{\real}{\operatorname{Re}} \newcommand{\imag}{\operatorname{Im}} \newcommand{\Arg}{\operatorname{Arg}} \newcommand{\Ln}{\operatorname{Ln}} \DeclareMathOperator*{\res}{res} \newcommand{\re}{\operatorname{Re}} \newcommand{\im}{\operatorname{Im}} \newcommand{\arsinh}{\operatorname{ar\,sinh}} \newcommand{\arcosh}{\operatorname{ar\,cosh}} \newcommand{\artanh}{\operatorname{ar\,tanh}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\diag}{\operatorname{diag}} \newcommand{\proj}{\operatorname{proj}} \newcommand{\rref}{\operatorname{rref}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\Span}{\operatorname{span}} \newcommand{\vir}{\operatorname{span}} \renewcommand{\dim}{\operatorname{dim}} \newcommand{\alg}{\operatorname{alg}} \newcommand{\geom}{\operatorname{geom}} \newcommand{\id}{\operatorname{id}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\tp}[1]{#1^{\top}} \renewcommand{\d}{\mathrm{d}} \newcommand{\sij}[2]{\bigg/_{\mspace{-15mu}#1}^{\,#2}} \newcommand{\abs}[1]{\lvert#1\rvert} \newcommand{\pysty}[1]{\left[\begin{array}{@{}r@{}}#1\end{array}\right]} \newcommand{\piste}{\cdot} \newcommand{\qedhere}{} \newcommand{\taumatrix}[1]{\left[\!\!#1\!\!\right]} \newenvironment{augmatrix}[1]{\left[\begin{array}{#1}}{\end{array}\right]} \newenvironment{vaugmatrix}[1]{\left|\begin{array}{#1}}{\end{array}\right|} \newcommand{\trans}{\mathrm{T}} \newcommand{\EUR}{\text{\unicode{0x20AC}}} \newcommand{\SI}[3][]{#2\,\mathrm{#3}} \newcommand{\si}[2][]{\mathrm{#2}} \newcommand{\num}[2][]{#2} \newcommand{\ang}[2][]{#2^{\circ}} \newcommand{\meter}{m} \newcommand{\metre}{\meter} \newcommand{\kilo}{k} \newcommand{\kilogram}{kg} \newcommand{\gram}{g} \newcommand{\squared}{^2} \newcommand{\cubed}{^3} \newcommand{\minute}{min} \newcommand{\hour}{h} \newcommand{\second}{s} \newcommand{\degreeCelsius}{^{\circ}C} \newcommand{\per}{/} \newcommand{\centi}{c} \newcommand{\milli}{m} \newcommand{\deci}{d} \newcommand{\percent}{\%} \newcommand{\Var}{\operatorname{Var}} \newcommand{\Cov}{\operatorname{Cov}} \newcommand{\Corr}{\operatorname{Corr}} \newcommand{\Tasd}{\operatorname{Tasd}} \newcommand{\Ber}{\operatorname{Ber}} \newcommand{\Bin}{\operatorname{Bin}} \newcommand{\Geom}{\operatorname{Geom}} \newcommand{\Poi}{\operatorname{Poi}} \newcommand{\Hyperg}{\operatorname{Hyperg}} \newcommand{\Tas}{\operatorname{Tas}} \newcommand{\Exp}{\operatorname{Exp}} \newcommand{\tdist}{\operatorname{t}} \newcommand{\rd}{\mathrm{d}}\]

Induktiotodistus¶

Kuvitellaan pitkä jono dominopalikoita. Milloin ne kaikki saadaan kaatumaan koskemalla vain jonon ensimmäiseen palikkaan? Videon perusteella voitaisiin muotoilla ehdot:

Ensimmäinen palikka saadaan kaadettua.
Jokainen kaatuva palikka kaataa myös seuraavan palikan.

Näistä molempien on toteuduttava, jotta kaikki palikat kaatuvat. Tulkitaan nyt jokainen dominopalikka väitteeksi \(P(n)\), jonka sisältö riippuu palikan järjestysnumerosta \(n\) jonossa. Jos jonon \(k\). palikka kaatuu, lause \(P(k)\) on tosi. Jos puolestaan \(k\). palikka kaatuessaan kaataa myös palikan \(k + 1\), niin lause \(P(k) \Rightarrow P(k + 1)\) pätee.

Mitä tapahtuu, jos lause \(P(1)\) on tosi ja lause \(P(k) \Rightarrow P(k + 1)\) on tosi kaikilla \(k\in\N\)?

Lause 1.6.1 (Induktioperiaate)

Olkoon \(n\) luonnollinen luku ja \(P(n)\) sitä koskeva väite. Jos

lause \(P(1)\) on tosi
aina, kun \(k \in \N\), lause \(P(k) \Rightarrow P(k + 1)\) on tosi

niin lause \(P(n)\) on tosi jokaisella \(n \in \N\).

Matemaattinen induktio, eli induktioperiaate perustelee hyvin erityisen todistusmenetelmän. Vaikka induktiotodistus soveltuu monipuolisempiinkin tapauksiin, keskitytään tässä tapaukseen, jossa todistettava väite \(P(n)\) koskee peräkkäisiä luonnollisia lukuja, tai yleisemmin jostain yksittäisestä luvusta alkaen kaikkia sitä suurempia kokonaislukuja. Induktiotodistuksella on seuraavissa esimerkeissä esiteltävä yksinkertainen rakenne. Esimerkeissä käytetään induktioperiaatteen kohdassa 2 esiintyvän implikaation \(P(k) \Rightarrow P(k + 1)\) kahdesta osasta nimityksiä induktio-oletus \(P(k)\) ja induktioväite \(P(k + 1)\).

Esimerkki 1.6.2

Osoita, että \(\displaystyle \sum_{j=1}^n j = 1+2+3+\cdots+n=\dfrac{n(n+1)}{2}\), kun \(n\in\N\).

Piilota/näytä todistus

Todistetaan tämä \(n\):n ensimmäisen luonnollisen luvun summaa koskeva väite induktiolla. Huomaa, että tapauksessa \(n = 1\) pitää ottaa ”yhden ensimmäisen luonnollisen luvun summa”. Toisin sanoen, silloin kun summausmerkinnässä on yläindeksin \(n\) paikalle sijoitettuna luku 1, on summasta huomioitava vain ensimmäisenä esiintyvä alkio, joka tässä tapauksessa on ykkönen. Yksittäistä alkiota ei yleensä mielletä varsinaisesti summaksi, mutta summausmerkintää käytettäessä se hyväksytään summan erikoistapaukseksi.

Alkuaskel. Kun \(n=1\), väite tulee muotoon

\[1 = \frac{1 \cdot (1 + 1)}{2} = 1,\]

mikä on tosi.
Induktioaskel. Tehdään induktio-oletus, jonka mukaan

\[1 + 2 + 3 + \ldots + k = \frac{k(k + 1)}{2},\]

kun \(k\) on luonnollinen luku. Pyritään osoittamaan todeksi induktioväite

\[1 + 2 + 3 + \ldots + k + (k + 1) = \frac{(k + 1)(k + 2)}{2}.\]

Induktio-oletuksen nojalla voidaan kirjoittaa

\[\begin{split}\begin{aligned} 1 + 2 + 3 + \ldots + k + (k + 1) &= (1 + 2 + 3 + \ldots + k) + (k + 1) \\ &\stackrel{\text{io}}{=} \left(\frac{k(k + 1)}{2}\right) + k + 1 \\ &= \frac{k(k + 1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}, \end{aligned}\end{split}\]

eli induktioväite on tosi.

Induktioperiaatteen nojalla siis

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

kaikilla luonnollisilla luvuilla \(n\).

Huomautus 1.6.3

Huomaa ero alkuperäisessä todistettavassa väitteessä ja induktio-oletuksessa. Todistettavan väitteen halutaan pätevän kaikille \(n \in \N\). Induktio-oletuksessa oletetaan, että on olemassa \(k\), jolle väitteessä esiintyvä yhtäsuuruus pätee, eli että yksi alkio toteuttaa sen kaavan, joka piti todistaa suuremmalle joukolle alkioita. Induktio-oletuksenkin voisi kirjoittaa käyttäen muuttujaa \(n\), mutta näissä esimerkeissä halutaan korostaa sitä, että kun kaava kirjoitetaan muuttujan \(k\) kanssa, silloin käsitellään nimenomaan yksittäistä mutta yksilöimätöntä alkiota.

Esimerkki 1.6.4

Todista Bernoullin epäyhtälö: jos \(1 + x \geq 0\), missä \(x \in \R\), niin

\[(1 + x)^n \geq 1 + nx\]

jokaiselle luonnolliselle luvulle \(n\).

Piilota/näytä todistus

Olkoon \(1 + x \geq 0\). Todistetaan väite induktiolla.

Alkuaskel. Kun \(n = 1\), väite tulee muotoon \((1 + x)^1 \geq 1 + x\), mikä on tosi.
Induktioaskel. Tehdään induktio-oletus, jonka mukaan \((1 + x)^k \geq 1 + kx\), kun \(k\) on eräs luonnollinen luku. Pyritään osoittamaan, että \((1 + x)^{k + 1} \geq 1 + (k + 1)x\). Induktio-oletuksen ja luvun \(x\) määrittelyn nojalla voidaan kirjoittaa

\[\begin{split}\begin{aligned} (1 + x)^{k + 1} &= (1 + x)^k(1 + x) \\ &\stackrel{\text{io}}{\geq} (1 + kx)(1 + x) \\ &= 1 + x + kx + kx^2 = 1 + (k + 1)x + \underbrace{kx^2}_{\geq 0} \\ &\geq 1 + (k + 1)x, \end{aligned}\end{split}\]

eli induktioväite on tosi.

Induktioperiaatteen nojalla siis \((1 + x)^{n} \geq 1 + nx\) kaikilla luonnollisilla luvuilla \(n\).

Induktiotodistuksen alkuaskeleessa voidaan valita myös mikä tahansa muu luonnollinen luku kuin \(1\). Tällöin väite tulee todistetuksi vain tätä suuremmille luvuille.

Esimerkki 1.6.5

Tutki, mistä luonnollisen luvun \(n\) arvosta alkaen \(2^n \leq n!\), ja todista väitteesi induktiolla. Luvun \(n\) kertoma (factorial) \(n!\) määritellään asettamalla

\[n!=1\cdot2\cdot3\cdot\cdots\cdot n.\]

Piilota/näytä ratkaisu

Tutkitaan lausekkeita \(2^n\) ja \(n!\), kun \(n = 1, 2, 3, \ldots\).

\[\begin{split}\begin{aligned} 2^1 = 2 &> 1 = 1!, & 2^2 = 4 &> 2 = 1 \cdot 2 = 2!, \\ 2^3 = 8 &> 6 = 1 \cdot 2 \cdot 3 = 3!,\qquad & 2^4 = 16 &\leq 24 = 1 \cdot 2 \cdot 3 \cdot 4 = 4!. \end{aligned}\end{split}\]

Siis kun \(n = 4\), lause \(2^n \leq n!\) on tosi. Todistetaan induktiolla, että \(2^n \leq n!\) aina, kun luonnollinen luku \(n \geq 4\).

Alkuaskel. Tapaus \(n = 4\) käsiteltiin jo.
Induktioaskel. Tehdään induktio-oletus, jonka mukaan \(2^k \leq k!\), kun \(k \geq 4\) on luonnollinen luku. Pyritään osoittamaan, että \(2^{k + 1} \leq (k + 1)!\). Koska \(k \geq 4\), niin \(2 < k + 1\), jolloin induktio-oletuksen nojalla voidaan kirjoittaa

\[2^{k + 1} = 2 \cdot 2^k \stackrel{\text{io}}{\leq} 2 \cdot k! < k!(k + 1) = (k + 1)!,\]

eli induktioväite on tosi.

Induktioperiaatteen nojalla siis \(2^n \leq n!\) kaikilla luonnollisilla luvuilla \(n \geq 4\).

Osoitetaan vielä seuraava lemma haastavampana esimerkkinä induktiotodistuksesta.

Lemma 1.6.6

Jos \(a\) ja \(b\) ovat reaalilukuja ja \(n>0\) luonnollinen luku, niin

\[a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+ab^{n-2}+b^{n-1})=(a-b)\sum_{i=1}^{n}a^{n-i}b^{i-1}.\]

Yllä sovitaan, että \(a^0=1=b^0\) myös, kun \(a=0\) tai \(b=0\). Erityisesti voidaan kirjoittaa seuraavat kaavat.

\[\begin{split}\begin{aligned} a^1-b^1&=(a-b)\\ a^2-b^2&=(a-b)(a+b)\\ a^3-b^3&=(a-b)(a^2+ab+b^2) \end{aligned}\end{split}\]

Piilota/näytä todistus

Alkuaskel. Väite pätee, kun \(n = 1\), sillä

\[a^1-b^1= (a-b)\cdot 1=(a-b)(a^0b^0)=(a-b)\sum_{i=1}^{1}a^{1-i}b^{i-1}.\]
Induktioaskel. Tehdään induktio-oletus, jonka mukaan

\[a^k-b^k =(a-b)\sum_{i=1}^{k}a^{i-k}b^{i-1},\]

kun \(k>1\) on luonnollinen luku. Täytyy osoittaa, että

\[a^{k+1}-b^{k+1} =(a-b)\sum_{i=1}^{k+1}a^{k+1-i}b^{i-1}.\]

Lähdetään liikkeelle todistettavan yhtälön vasemmasta puolesta ja pyritään kirjoittamaan se muodossa, johon voidaan käyttää induktio-oletusta. Kirjoitetaankin \(a^{k+1}=aa^k\), \(b^{k+1}=bb^k\) ja lisätään ja vähennetään termi \(ba^k\), jolloin

\[\begin{split}\begin{aligned} a^{k+1}-b^{k+1}& =a a^{k} -b a^k + b a^k-bb^{k} \\ & = a^k(a-b)+b(a^k-b^k)\\ & = a^k(a-b)+b(a-b)\sum_{i=1}^{k}a^{k-i}b^{i-1} & & \text{induktio-oletus}\\ & = (a-b)\left(a^k+b\sum_{i=1}^{k}a^{k-i}b^{i-1}\right)\\ & = (a-b)(a^k+b(a^{k-1}+a^{k-2}b+\cdots+b^{k-1}))\\ & = (a-b)(a^k+a^{k-1}b+a^{k-2}b^2+\cdots+b^{k}))\\ & = (a-b)\sum_{i=1}^{k+1}a^{k+1-i}b^{i-1}, \end{aligned}\end{split}\]

eli induktioväite on tosi.

Tarkastellaan seuraavaa induktiotodistusta. Tarkoituksena on täydentää siitä löytyvien tyhjät kohdat, jotka on merkitty kirjaimilla.

Todistetaan, että \(2^n > 4n\), kun \(n \in \N\) ja \(n > 4\).

Alkuaskel. Tarkistetaan, että väite pätee luvulla \(n = \underline{\phantom{5}}\) (a). Tällöin \(2^n=\underline{\phantom{32}}\) (b) ja \(4n=\underline{\phantom{20}}\) (c), joten väite on voimassa, kun \(n=\underline{\phantom{5}}\) (d).
Induktioaskel. Tehdään induktio-oletus, jonka mukaan väite on voimassa jollekin \(k \in \N\), \(k >4\). Oletetaan siis, että \(2^k > 4k\). Näytetään sitten, että väite pätee tällöin myös luvulla \(\underline{\phantom{k + 1}}\) (e). 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).\]

Välivaiheessa \(\underline{\phantom{3}}\) (f) käytettiin induktio-oletusta ja kohdassa \(\underline{\phantom{4}}\) (g) tietoa \(k > 4\) (syötä kohtiin (f) ja (g) oikean välivaiheen numero \(1\)–\(5\)).

Niinpä alku- ja induktioaskeleesta seuraa induktioperiaatteen nojalla, että \(2^n > 4n\), kun \(n \in \N\) ja \(n > 4\).

Täytä kirjaimin merkityt kohdat tänne.

Kysymys 1

Kohta (a)

Kysymys 2

Kohta (b)

Kysymys 3

Kohta (c)

Kysymys 4

Kohta (d)

Kysymys 5

Kohta (e)

Kysymys 6

Kohta (f)

Kysymys 7

Kohta (g)

Induktiotodistuksen kanssa tulee olla tarkkana, että induktioperiaatteen kumpikin ehto on voimassa. Pohdi, mikä seuraavien esimerkkien ”todistuksissa” menee väärin.

Esimerkki 1.6.7

”Osoitetaan” induktiolla, että \(n > n + 1\) kaikilla luonnollisilla luvuilla \(n\).

Piilota/näytä ratkaisu

Induktio-oletuksena on nyt, että \(k > k + 1\) jollakin luonnollisella luvulla \(k\). Pyritään näyttämään induktioväite todeksi. Induktio-oletuksen mukaan

\[k + 1 > (k + 1) + 1,\]

eli induktioväite pätee.

Näin ollen \(n > n + 1\) kaikilla luonnollisilla luvuilla \(n\). \(\boxtimes\)

Esimerkki 1.6.8

”Osoitetaan” induktiolla, että jos lammaslaumassa on vähintään yksi musta lammas, niin kaikki lauman lampaat ovat mustia.

Piilota/näytä ratkaisu

Koska väite koskee mielivaltaista lammaslaumaa, jossa on vähintään yksi musta lammas, tehdään induktiotodistus lauman koon suhteen.

Alkuaskel. Tarkastellaan yhden lampaan laumaa. Jos lauman ainoa lammas on musta, niin kaikki lauman lampaat ovat tällöin mustia. Väite pitää siis paikkansa.
Induktioaskel. Tehdään induktio-oletus, jonka mukaan \(k\):n lampaan laumassa kaikki lampaat ovat mustia, jos vähintään yksi lampaista on musta. Tässä \(k > 1\) on jokin luonnollinen luku. Pyritään osoittamaan, että jos laumassa, jossa on \(k + 1\) lammasta, vähintään yksi lammas on musta, niin lauman kaikki lampaat ovat mustia.

Oletetaan, että laumassa, jossa on \(k+1\) lammasta, on vähintään yksi musta lammas. Tällöin laumasta voidaan muodostaa \(k\):n lampaan lauma siten, että vähintään yksi musta lammas kuuluu laumaan. Induktio-oletuksen mukaan tämän lauman kaikki lampaat ovat mustia.

Nyt laumasta on jäljellä enää yksi epämääräisen värinen lammas, joka jäi yli, kun muodostettiin \(k\):n lampaan lauma. Muodostetaan uusi \(k\):n lampaan lauma, johon tämä lammas kuuluu. Koska tässä laumassa on vähintään yksi musta lammas, voidaan induktio-oletuksen perusteella todeta, että epämääräisen värisenkin lampaan on oltava musta. Siispä lauman, jossa on \(k+1\) lammasta, kaikki lampaat ovat mustia, eli induktioväite on tosi.

Induktioperiaatteen nojalla väite on tosi. \(\boxtimes\)