Metoda inducției matematice

Pasul 1 din 9

Un tipar

Adună numerele impare, pe rând:

{1 = 1}

{1 + 3 = 4}

{1 + 3 + 5 = 9}

{1 + 3 + 5 + 7 = 16}

$1+3+5+7=16=4^2$

Fiecare număr impar e un „L” care mărește pătratul cu un rând și o coloană. Ghicim:

$S_n = 1 + 3 + 5 + \dots + (2n - 1) = n^2.$

Dar am verificat doar 4 cazuri. Ajunge o presupunere?

Atenție la generalizări pripite

Matematicianul Pierre Fermat (1601–1665) a studiat numerele de forma

2^{2^n} + 1

, cu

n \in \mathbb{N}

$n$	$2^{2^n} + 1$	e prim?
$0$	$3$	da
$1$	$5$	da
$2$	$17$	da
$3$	$257$	da
$4$	$65\,537$	da

Toate cele cinci sunt prime. Fermat a crezut că așa e pentru orice

n

Verifică-te

Fie

P(n)

: „

2^{2^n} + 1

este prim”. Știm că

P(0), \dots, P(4)

sunt adevărate. Este

P(n)

adevărată pentru orice

n \in \mathbb{N}

Domino

Ai un șir de piese de domino, fără sfârșit. Ca să fii sigur că toate cad, îți ajung două lucruri:

I. Prima piesă cade (o împingi tu).

II. Oricare piesă, dacă cade, o dărâmă pe următoarea.

Din I cade prima. Din II cade a doua, apoi a treia, și tot așa. Nu trebuie să vezi fiecare piesă căzând.

Etapele, pe exemplul nostru

$P(n)$ : „ $S_n = n^2$ ”, unde ${S_n = 1 + 3 + \dots + (2n - 1)}$ și $n \ge 1$ .

Etapa I (prima piesă). $P(1)$ : $1 = 1^2$ . Adevărat.

Etapa II (o piesă o dărâmă pe următoarea). Fie $k \ge 1$ . Nu știm încă dacă $P(k)$ e adevărată. Arătăm doar că, dacă este, atunci și $P(k + 1)$ este.

Presupunem deci $S_k = k^2$ . Suma $S_{k+1}$ are în plus următorul număr impar, $2k + 1$ :

\begin{aligned} S_{k+1} &= S_k + (2k + 1) \\ &= k^2 + 2k + 1 = (k + 1)^2 \end{aligned}

P(1)

\Rightarrow

P(2)

\Rightarrow

P(3)

\Rightarrow

\dots

Etapa I împinge prima piesă, iar etapa II le dărâmă, pe rând, pe toate. Deci

P(n)

e adevărată pentru orice

n \ge 1

De ce funcționează?

$1+3+5+7=16=4^2$

Etapa II, desenată. Pătratul $3 \times 3$ are 9 pătrățele. Îi lipim un „L” de $2 \cdot 3 + 1 = 7$ pătrățele și obținem pătratul $4 \times 4$ .

La fel pentru orice $k$ : un rând de $k$ , o coloană de $k$ și colțul fac $2k + 1$ pătrățele, iar pătratul $k \times k$ devine ${(k + 1) \times (k + 1)}$ . Manualul numește asta „demonstrație fără cuvinte”.

Verifică-te

Vrei să demonstrezi

{1 + 2 + \dots + n = \frac{n(n + 1)}{2}}

. În etapa II, ce adaugi la suma până la

k

ca să obții suma până la

k + 1

Nu începem mereu de la 1

Până acum prima piesă a fost

P(1)

. Ea poate fi și

P(0)

(în manual,

0 \in \mathbb{N}

) sau chiar una mai încolo. Compară

2^n

n^2

$n$	$2^n$	$n^2$	$2^n > n^2$ ?
$0$	$1$	$0$	A
$1$	$2$	$1$	A
$2$	$4$	$4$	F
$3$	$8$	$9$	F
$4$	$16$	$16$	F
$5$	$32$	$25$	A
$6$	$64$	$36$	A
$7$	$128$	$49$	A

Verifică-te

Vrei să demonstrezi prin inducție că

2^n > n^2

. De la ce

n

pornești?

Pasul II la inegalitate

$2^n$
$n^2$

$P(n)$ : „ $2^n > n^2$ ”, pentru $n \ge 5$ . Etapa I: $32 > 25$ .

Etapa II. Fie $k \ge 5$ . Dacă $2^k > k^2$ (ipoteza de inducție), dublăm:

2^{k+1} = 2 \cdot 2^k > 2k^2

Mai trebuie ${2k^2 \ge (k + 1)^2}$ , adică ${k^2 \ge 2k + 1}$ . Pentru $k \ge 5$ : ${k^2 \ge 5k = 2k + 3k > 2k + 1}$ . Rezultă ${2^{k+1} > 2k^2 \ge (k + 1)^2}$ , adică $P(k + 1)$ e adevărată.

Deci $P(n)$ e adevărată pentru orice $n \ge 5$ .

Fără prima piesă nu merge

Cineva susține că ${1 + 2 + \dots + n = \frac{n^2 + n + 2}{2}}$ .

Etapa II merge: dacă formula ar fi adevărată pentru $k$ , adăugăm $k + 1$ :

\begin{aligned} &1 + \dots + k + (k + 1) \\ &= \frac{k^2 + k + 2}{2} + (k + 1) \\ &= \frac{k^2 + 3k + 4}{2} \\ &= \frac{(k + 1)^2 + (k + 1) + 2}{2} \end{aligned}

Exact formula pentru

k + 1

. Acum câteva valori:

$n$	$1 + \dots + n$	$\frac{n^2 + n + 2}{2}$
$1$	$1$	$2$
$2$	$3$	$4$
$3$	$6$	$7$
$4$	$10$	$11$

Verifică-te

Ce nu merge în această „demonstrație”?

Cum scrie manualul

Fie $m \in \mathbb{N}$ fixat și un predicat $p(n)$ , $n \in \mathbb{N}$ , $n \ge m$ . Ca să arătăm că ${(\forall)\, n \ge m,\ p(n)}$ este adevărată, verificăm două etape:

I. Etapa de verificare (inițială): $p(m)$ este adevărată ( $m$ este valoarea de inițiere).

II. Etapa de demonstrație (pasul de inducție propriu-zis): implicația ${p(k) \to p(k + 1)}$ este adevărată pentru orice $k \in \mathbb{N}$ , $k \ge m$ . Aici $p(k)$ se numește ipoteza de inducție.

Dacă ambele etape au loc, $p(n)$ e adevărată pentru orice $n \ge m$ . Metoda se mai numește principiul inducției matematice.