Inducția matematică

Principiul inducției matematice

Servește la demonstrarea unei propoziții $P(n)$ pentru toate numerele naturale $n \ge n_0$.

Ideea: dacă poți urca pe prima treaptă, și dacă de pe orice treaptă poți urca pe următoarea, atunci ajungi pe orice treaptă.

Cele două etape

1. Verificarea (baza): arăți că $P(n_0)$ e adevărată. De obicei $n_0 = 1$.

2. Pasul inductiv: presupui că $P(k)$ e adevărată pentru un $k \ge n_0$ oarecare (ipoteza de inducție) și demonstrezi că atunci și $P(k+1)$ e adevărată.

Dacă ambele reușesc, $P(n)$ e adevărată pentru orice $n \ge n_0$.

Ambele etape sunt obligatorii. Fără verificare, pasul inductiv nu are de unde porni.

Exemplu rezolvat

Demonstrează că $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$.

Verificare pentru $n = 1$: membrul stâng e 1, membrul drept e $\dfrac{1 \cdot 2}{2} = 1$. Adevărat.

Pas inductiv: presupunem $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$.

Adăugăm $k+1$ în ambii membri:

$1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$

Dăm factor comun $(k+1)$:

$= (k+1)\left(\frac{k}{2} + 1\right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$

Exact formula pentru $n = k+1$. Demonstrația e încheiată.

Al doilea exemplu

Demonstrează că $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

Verificare pentru $n=1$: stânga 1, dreapta $\dfrac{1 \cdot 2 \cdot 3}{6} = 1$. Adevărat.

Pas inductiv: adăugăm $(k+1)^2$ la ipoteză și trebuie să obținem $\dfrac{(k+1)(k+2)(2k+3)}{6}$. Se dă factor comun $\dfrac{k+1}{6}$ și rămâne de verificat că $k(2k+1) + 6(k+1) = (k+2)(2k+3)$, adică $2k^2 + 7k + 6$ în ambii membri.

Formule utile

$1 + 2 + \dots + n = \frac{n(n+1)}{2}$ $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ $1^3 + 2^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$

Ultima are o consecință elegantă: suma cuburilor e pătratul sumei numerelor.

Greșeli frecvente

1. Se sare peste verificarea inițială.
2. Se presupune $P(n)$ pentru toate valorile, ceea ce echivalează cu a presupune concluzia. Se presupune doar pentru un $k$ fixat.
3. Se verifică pentru câteva valori și se trage concluzia generală. Verificarea a zece cazuri nu e demonstrație.