Inducția matematică

Inducția matematică este o metodă de demonstrație pentru afirmații $P(n)$ despre toate numerele naturale de la un anumit prag. Are doi pași. Mai întâi verifici afirmația la valoarea inițială $n_0$. Apoi presupui că este adevărată pentru un $n\ge n_0$ arbitrar și demonstrezi, folosind această ipoteză, că este adevărată și pentru $n+1$. Cei doi pași împreună acoperă toate valorile cerute; verificarea câtorva exemple nu este o demonstrație generală.

Exemplu rezolvat. Demonstrează $1+2+\cdots +n=n(n+1)/2$ pentru $n\ge 1$.

1. Baza: pentru $n=1$, stânga este $1$, iar dreapta este $1(1+1)/2=1$.
2. Ipoteza: presupune $1+\cdots +n=n(n+1)/2$.
3. Adaugă termenul următor: $1+\cdots +n+(n+1)=n(n+1)/2+(n+1)$.
4. Scoate factor comun: $(n+1)(n+2)/2$, exact formula cu $n$ înlocuit de $n+1$.

Concluzie: afirmația este adevărată pentru toate $n\ge 1$.

Principiul inducției matematice: dacă $P(n_0)$ este adevărată și, pentru fiecare $n\ge n_0$, implicația $P(n)\Rightarrow P(n+1)$ este adevărată, atunci $P(n)$ este adevărată pentru toate numerele naturale $n\ge n_0$. Pasul de inducție este deci implicația pentru un $n$ arbitrar din domeniul cerut. Nu este suficient să arăți că $P(n+1)$ este adevărată folosind chiar $P(n+1)$; aceasta ar fi un raționament circular. Uneori se folosește inducția completă: se presupun toate afirmațiile de la $n_0$ la $n$ pentru a demonstra $P(n+1)$. Dacă pasul face salturi de două unități, pot fi necesare două baze separate. Baza nu este întotdeauna $n=1$: afirmația se poate demonstra de la un prag $n_0$, iar pentru valorile mai mici ea poate fi chiar falsă.

Exemplu rezolvat. Demonstrăm că suma primelor $n$ numere impare este $1+3+\cdots +(2n-1)=n^2$, pentru $n\ge 1$.

1. Baza: la $n=1$, ambele părți sunt $1$.
2. Presupunem că suma primelor $n$ numere impare este $n^2$.
3. Următorul termen este $2(n+1)-1=2n+1$, deci noua sumă este $n^2+2n+1$.
4. Cum $n^2+2n+1=(n+1{)}^2$, formula este adevărată și pentru $n+1$.

Prin principiul inducției, formula este valabilă pentru orice $n\ge 1$.

Exemplu rezolvat. Demonstrăm că $2^n>n^2$ pentru orice $n\ge 5$. Afirmația este falsă pentru $n=2;3;4$ (de exemplu, $2^4=16=4^2$), deci baza este $n_0=5$.

1. Baza: $2^5=32>25=5^2$.
2. Ipoteza: pentru un $n\ge 5$ avem $2^n>n^2$.
3. Înmulțim cu $2$: $2^{n+1}>2n^2$.
4. Arătăm că $2n^2\ge (n+1{)}^2$. Inegalitatea este echivalentă cu $n^2-2n-1\ge 0$, adică $(n-1{)}^2\ge 2$, adevărată pentru $n\ge 3$, deci în particular pentru $n\ge 5$.
5. Rezultă $2^{n+1}>2n^2\ge (n+1{)}^2$.

Afirmația este adevărată pentru orice $n\ge 5$.

Exemplu rezolvat. Demonstrăm că $7\mid 8^n-1$ pentru orice $n\ge 1$.

1. Baza: $8^1-1=7$, divizibil cu $7$.
2. Ipoteza: $8^n-1=7k$, cu $k$ număr natural.
3. Pasul: $8^{n+1}-1=8\cdot 8^n-1=8(8^n-1)+8-1=8\cdot 7k+7=7(8k+1)$.
4. Cum $8k+1$ este număr natural, $7\mid 8^{n+1}-1$.

Exemplu rezolvat. Un șir este dat prin $a_1=1$ și $a_{n+1}=2a_n+1$. Demonstrăm că $a_n=2^n-1$ pentru orice $n\ge 1$.

1. Baza: $a_1=1=2^1-1$.
2. Ipoteza: $a_n=2^n-1$.
3. Pasul: $a_{n+1}=2a_n+1=2(2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1$.

Primii termeni confirmă formula: $a_2=3$, $a_3=7$, $a_4=15$. Inducția este metoda naturală pentru șiruri definite prin recurență, deoarece pasul de inducție repetă exact legătura dintre doi termeni consecutivi.

Inducția completă se folosește atunci când pasul are nevoie de mai mulți termeni anteriori. De exemplu, la un șir cu $a_{n+1}=a_n+a_{n-1}$, pasul pentru $n+1$ apelează la $P(n)$ și la $P(n-1)$, deci ipoteza trebuie să cuprindă ambele afirmații, iar baza are două cazuri: $n=1$ și $n=2$.

Trucul pasului este rescrierea expresiei de rangul $n+1$ astfel încât să apară expresia de rangul $n$, pentru care avem ipoteza. La sume, aceasta înseamnă separarea ultimului termen; la divizibilități, adăugarea și scăderea unui termen potrivit; la inegalități, înmulțirea ipotezei cu un număr pozitiv.

La admitere inducția apare ca demonstrație a unei formule de sumă, a unei divizibilități sau a unei inegalități, uneori cu mai multe formule propuse dintre care se alege cea corectă. Se verifică întâi candidatele pe primele valori ($n=1$, apoi $n=2$), iar pentru formula rămasă se face pasul de inducție.

Problemă rezolvată. Suma $S_n=1\cdot 2+2\cdot 3+\cdots +n(n+1)$ este egală cu:

a) $\frac{n(n+1)(n+2)}{3}$ b) $\frac{n(n+1)}{2}$ c) $\frac{n(n+1)(2n+1)}{6}$ d) $\frac{n(n+1)(n+2)}{6}$ e) $\frac{n^2(n+1)}{2}$ f) $\frac{n(n+1)(n+3)}{4}$

1. Pentru $n=1$, $S_1=2$. Variantele b), c), d), e) dau $1$, deci se elimină. Rămân a) și f).
2. Pentru $n=2$, $S_2=2+6=8$. Varianta a) dă $2\cdot 3\cdot 4/3=8$, iar f) dă $7,5$, deci f) se elimină.
3. Pasul de inducție pentru a): dacă $S_n=\frac{n(n+1)(n+2)}{3}$, atunci $S_{n+1}=\frac{n(n+1)(n+2)}{3}+(n+1)(n+2)=\frac{(n+1)(n+2)(n+3)}{3}$, adică formula pentru $n+1$.

Răspuns corect: a). Variantele b) și c) sunt sumele $1+2+\cdots +n$ și $1^2+2^2+\cdots +n^2$, adică formule memorate pentru alte sume; d) este varianta a) cu numitorul dublu, greșeală la factorul constant; f) trece de testul pentru $n=1$, dar nu și pe cel pentru $n=2$.

Verificarea rapidă a candidatelor pe valori mici economisește timp: pe grilă nu se cere demonstrația completă, ci formula corectă, iar eliminarea variantelor cu $n=1$ și $n=2$ lasă de obicei o singură variantă. Pasul de inducție rămâne metoda sigură atunci când două variante coincid pe valorile testate. Cu formula aleasă, $S_{10}=\frac{10\cdot 11\cdot 12}{3}=440$.

Greșeli frecvente

• Greșit: A verifica numai primele trei valori și a declara afirmația demonstrată.
  Corect: sunt necesare cazul inițial și pasul general.
• Greșit: A uita cazul inițial.
  Corect: cazul inițial se demonstrează explicit; fără el, pasul $P(n)\Rightarrow P(n+1)$ nu pornește de nicăieri (pentru $P(n)$: „$n=n+1$”, implicația $P(n)\Rightarrow P(n+1)$ este adevărată, dar $P(1)$ este falsă).
• Greșit: A presupune direct ținta $P(n+1)$ în loc să pornească de la $P(n)$.
  Corect: în pasul inductiv se presupune $P(n)$ și se deduce $P(n+1)$.

Înainte și după