4.4 Induktiotodistus

Teoria ja esimerkit

Luonnollisten lukujen ℕ = {0, 1, 2, 3, …} ja positiivisten kokonaislukujen ℤ₊ = {1, 2, 3, …} joukossa pätee induktio-ominaisuus:

- Jos jokin ominaisuus pätee jollekin luvulle n (ekalle luvulle)
JA
- Jos siitä, että väite pätee arvolla n = k seuraa, että väite pätee myös arvolla k + 1, niin väite pätee kaikilla arvoilla n.

Induktiotodistus

Alkuaskel: Osoitetaan, että väite pätee, kun n = 0 (tai n = 1, kun n ∈ ℤ₊).

Induktioaskel: Oletetaan, että väite on tosi, kun n = k ja
todistetaan, että väite on tosi, kun n = k + 1.

(Näistä seuraa, että luvusta 0 (tai 1) alkaen väite pätee kaikilla muillakin luvuilla.)

ESIM 1. Osoita, että 2 + 4 + 6 + … + 2n = n(n + 1), kun n ∈ ℤ₊.

1) Alkuaskel:

kun n = 1, niin vasemmalla on 2, oikealla 1*(1+1) = 2

( kun n = 2, niin vasemmalla 2 + 4 = 6, oikealla 2*(2 + 1) = 6 )

( kun n = 3, niin vasemmalla 2 + 4 + 6 = 12, oikealla 3*(3 + 1) = 12 )

2) Induktioaskel:

Oletetaan, että 2 + 4 + 6 + ... + 2n = n(n + 1)

[ todistetaan, että 2 + 4 + 6 + ... + 2n + 2(n+1) = (n+1) ( n+1 + 1) = (n+1)(n +2) ]

2 + 4 + 6 + ... + 2n + 2(n+1) = n(n+1) + 2(n+1) = (n+1)(n + 2).

Siis askelista 1 ja 2 seuraa, että väite on tosi.

(testataan luvulla n = 10:

2+4+6+8+10+12+14+16+18+20 = 110

n(n+1) = 10(10 + 1) = 110

ESIM 2. Osoita, että $1^2+2^2+3^2+\ ...\ +\left(n-1\right)^2<\frac{n^3}{3}{,}\ \ \ \ \ \text{kun}\ n\in\mathbb{Z}_+$

Todistetaan induktiolla.

1) Alkuaskel: n = 1

Vasemmalla: $\left(1-1\right)^2=0^2=0$

Oikealla: $\frac{1}{3}$

0 < 1/3, joten pätee.

2) Induktioaskel: oletetaan, että pätee, kun n = k

eli $1^2+2^2+3^2+\ ...\ +\left(k-1\right)^2<\frac{k^3}{3}$

Todistetaan, että pätee, kun n = k + 1

eli että

$1^2+2^2+3^2+\ ...\ +\left(k-1\right)^2+\left(\left(k+1\right)-1\right)^2<\frac{\left(k+1\right)^3}{3}$

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

Siis askelista 1 ja 2 seuraa, että väite pätee.

-----------

HUOM! Lukujen summalle voi käyttää merkintää
$a_1+a_2+...+a_n=\sum_{k=1}^na_k$

--------

ESIM 3. Osoita, että $1^2+2^2+3^2+...+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$ , kun n ∈ ℤ+.

eli

$\sum_{k=1}^nk^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$ .

Todistetaan induktiolla.

1) Alkuaskel: n = 1

Vasemmalla: $1^2=1$

Oikealla: $\frac{1\left(1+1\right)\left(2\cdot1+1\right)}{6}=\frac{1\cdot2\cdot3}{6}=1$

Pätee.

2) Induktioaskel.

Oletetaan, että pätee, kun n = m eli

$\sum_{k=1}^mk^2=\frac{m\left(m+1\right)\left(2m+1\right)}{6}$ .

Todistetaan, että pätee, kun n = m + 1

eli että

$\sum_{k=1}^{m+1}k^2=\frac{\left(m+1\right)\left(m+2\right)\left(2\left(m+1\right)+1\right)}{6}=\frac{\left(m+1\right)\left(m+2\right)\left(2m+3\right)}{6}$ .

Todistus:

$\sum_{k=1}^{m+1}k^2=\left(\sum_{k=1}^mk^2\right)+\left(m+1\right)^2$

$=\frac{m\left(m+1\right)\left(2m+1\right)}{6}+\left(m+1\right)^2$
$=\frac{m\left(m+1\right)\left(2m+1\right)}{6}+\frac{6\left(m+1\right)\left(m+1\right)}{6}$

$=\frac{\left(m\left(2m+1\right)+6\left(m+1\right)\right)\left(m+1\right)}{6}$

$=\frac{\left(m\cdot2m+m\cdot1+6m+6\right)\left(m+1\right)}{6}$

$=\frac{\left(m\cdot2m+3m+4m+6\right)\left(m+1\right)}{6}$

$=\frac{\left(m\cdot\left(2m+3\right)+2\left(2m+3\right)\right)\left(m+1\right)}{6}$ $=\frac{\left(\left(m+2\right)\cdot\left(2m+3\right)\right)\left(m+1\right)}{6}$

$=\frac{\left(m+1\right)\left(m+2\right)\left(2m+3\right)}{6}$

Siis askelista 1 ja 2 seuraa, että väite pätee.