Metoda inducției matematice: principiul dominoului

Sigur ai văzut, măcar într-un clip, mii de piese de domino așezate în șir, răsturnate toate de o singură atingere. Ca să fii sigur că toate piesele cad, nu trebuie să le împingi pe fiecare în parte. Îți ajung două certitudini: că prima piesă cade și că piesele sunt așezate astfel încât oricare piesă, când cade, o dărâmă pe următoarea. Atât. Din aceste două fapte rezultă, fără nicio excepție, căderea tuturor pieselor — chiar dacă ar fi un milion.

Matematica are nevoie exact de un astfel de mecanism. De multe ori vrem să demonstrăm că o afirmație este adevărată pentru toate numerele naturale: pentru $n=1$, pentru $n=2$, pentru $n=100$, pentru orice $n$. Nu putem verifica o infinitate de cazuri unul câte unul — viața nu ne ajunge. Metoda inducției matematice este „dominoul" matematicii: verificăm prima piesă și demonstrăm că fiecare piesă o dărâmă pe următoarea. Este una dintre cele mai importante metode de demonstrație pe care le înveți la mate-info și te va însoți până la Bacalaureat și dincolo de el, în facultate și în informatică — unde stă la baza recursivității.

Ce vei învăța

• Vei ști de ce verificarea oricâtor cazuri particulare nu este o demonstrație — și vei vedea un exemplu celebru care „merge" de 40 de ori și apoi se strică.
• Vei ști să enunți principiul inducției matematice și să explici de ce funcționează, prin analogia cu dominoul.
• Vei ști să redactezi cele două etape ale unei demonstrații prin inducție: etapa de verificare și etapa de demonstrație (pasul inductiv).
• Vei ști să demonstrezi prin inducție formule de sume clasice, cum este suma lui Gauss $1+2+\cdots +n=\frac{n(n+1)}{2}$.
• Vei ști să depistezi demonstrațiile greșite prin inducție: ce se întâmplă când lipsește verificarea sau când pasul inductiv are o fisură.
• Vei ști să aplici inducția și atunci când afirmația e adevărată abia de la un rang încolo ($n\ge n_0$).

Hai să descoperim împreună

1. De ce nu ajunge să verificăm „multe" cazuri

Să privim expresia $E(n)=n^2+n+41$ și să calculăm câteva valori:

$$E(0)=41,E(1)=43,E(2)=47,E(3)=53,E(4)=61,E(5)=71.$$

Toate sunt numere prime! Continuăm: $E(6)=83$, $E(7)=97$, $E(8)=113$... tot prime. Poți verifica, cu răbdare, că $E(n)$ este prim pentru toate valorile $n=0,1,2,\dots ,39$. Patruzeci de succese la rând! Ai fi tentat să declari: „$E(n)$ este prim pentru orice $n$ natural".

Și totuși afirmația este falsă. Pentru $n=40$:

$$E(40)=40^2+40+41=1600+81=1681=41^2,$$

care nu este prim. Patruzeci de verificări nu au valorat, ca demonstrație, nimic.

Aceasta este lecția de fond: oricâte cazuri particulare am verifica, ele nu demonstrează o afirmație despre toate numerele naturale. Cazurile particulare pot cel mult să ne convingă că merită să căutăm o demonstrație — sau, dacă găsim un contraexemplu, să respingă afirmația definitiv. Pentru „demonstrat pentru orice $n$" ne trebuie altceva: un mecanism care să acopere infinitatea de cazuri dintr-o singură mișcare.

2. Principiul dominoului, spus matematic

Să notăm cu $P(n)$ o afirmație care depinde de numărul natural $n$ — de exemplu, $P(n)$: „$1+2+\cdots +n=\frac{n(n+1)}{2}$". Pentru fiecare valoare a lui $n$, $P(n)$ este o propoziție: $P(1)$, $P(2)$, $P(3)$ și așa mai departe — un șir infinit de propoziții, ca un șir infinit de piese de domino.

Principiul inducției matematice. Dacă:

1. $P(1)$ este adevărată (prima piesă cade), și
2. pentru orice $k\ge 1$, din $P(k)$ adevărată rezultă $P(k+1)$ adevărată (orice piesă care cade o dărâmă pe următoarea),

atunci $P(n)$ este adevărată pentru orice număr natural $n\ge 1$.

De ce putem avea încredere? Urmărește lanțul: $P(1)$ e adevărată din condiția 1. Aplicăm condiția 2 cu $k=1$: din $P(1)$ rezultă $P(2)$. Aplicăm din nou condiția 2, acum cu $k=2$: din $P(2)$ rezultă $P(3)$. Și tot așa: orice număr $n$ am alege, ajungem la el în $n-1$ pași siguri. Nicio propoziție din șir nu scapă. Ideea acestui raționament în lanț este rudă bună cu ceea ce ai studiat la Validarea logică a pașilor unui raționament: fiecare pas este o implicație corectă, iar concluzia se sprijină pe toate verigile de dinainte.

Reține vocabularul: condiția 1 se numește etapa de verificare (sau baza inducției), iar condiția 2 se numește etapa de demonstrație sau pasul inductiv. Presupunerea „$P(k)$ este adevărată", cu care lucrăm în pasul inductiv, poartă numele de ipoteză de inducție.

3. Cele două etape, pe curat

O demonstrație prin inducție se redactează întotdeauna după același tipar. Să-l scriem ca pe o rețetă:

Etapa I (verificarea). Arătăm că $P(1)$ este adevărată — de regulă printr-un calcul direct, scurt.

Etapa a II-a (demonstrația). Fixăm un $k\ge 1$ oarecare și presupunem că $P(k)$ este adevărată (ipoteza de inducție). Folosind această presupunere, demonstrăm că și $P(k+1)$ este adevărată.

Concluzia. Conform principiului inducției matematice, $P(n)$ este adevărată pentru orice $n\ge 1$.

Un punct sensibil, la care greșesc mulți elevi la început: în etapa a II-a nu presupunem ce aveam de demonstrat. Noi avem de demonstrat că $P(n)$ e adevărată pentru toate numerele $n$. În pasul inductiv presupunem doar că o singură propoziție din șir, $P(k)$, este adevărată, și arătăm că adevărul ei se transmite următoarei. E diferența dintre „presupun că toate piesele cad" (incorect, e chiar concluzia!) și „presupun că piesa $k$ cade și arăt că lovește piesa $k+1$" (corect, e doar o verigă).

4. Prima demonstrație completă: suma lui Gauss

Să demonstrăm prin inducție că pentru orice $n\ge 1$:

$$P(n):1+2+3+\cdots +n=\frac{n(n+1)}{2}.$$

Etapa I (verificarea). Pentru $n=1$: membrul stâng este $1$, iar membrul drept este $\frac{1\cdot 2}{2}=1$. Egalitatea are loc, deci $P(1)$ este adevărată.

Etapa a II-a (demonstrația). Fie $k\ge 1$ pentru care presupunem adevărată ipoteza de inducție:

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

Vrem să demonstrăm $P(k+1)$, adică:

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

Pornim de la membrul stâng și folosim ipoteza de inducție pentru primii $k$ termeni:

$$\underset{=\frac{k(k+1)}{2}}{\underbrace{1+2+\cdots +k}}+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}.$$

Am obținut exact membrul drept al lui $P(k+1)$, deci $P(k+1)$ este adevărată.

Concluzia. Conform principiului inducției matematice, egalitatea este adevărată pentru orice $n\ge 1$. $■$

Observă mișcarea-cheie, pe care o vei repeta în aproape orice inducție cu sume: am rupt suma de la $1$ la $k+1$ în suma de la $1$ la $k$ (pe care o cunoaștem din ipoteză) plus ultimul termen. Restul e calcul algebric — aici, scoaterea factorului comun $k+1$.

5. Cum redactezi la Bacalaureat

La examen, redactarea contează la fel de mult ca ideea. Iată scheletul pe care baremul îl așteaptă, cu formulările consacrate:

1. „Notăm cu $P(n)$ afirmația: …" — scrii explicit afirmația.
2. „Etapa de verificare. Pentru $n=1$ avem …, deci $P(1)$ este adevărată."
3. „Etapa de demonstrație. Presupunem că $P(k)$ este adevărată pentru un $k\ge 1$, adică … . Demonstrăm că $P(k+1)$ este adevărată, adică … ."
4. Calculul, în care marchezi clar locul unde folosești ipoteza de inducție (o acoladă sub sumă sau mențiunea „din ipoteza de inducție").
5. „Conform principiului inducției matematice, $P(n)$ este adevărată pentru orice $n\ge 1$."

Două recomandări de om pățit. Întâi: scrie explicit cum arată $P(k+1)$ înainte să te apuci de calcul — știi exact unde vrei să ajungi și nu te rătăcești. Apoi: la final compară, cuvânt cu cuvânt, rezultatul calculului cu ținta scrisă. Dacă diferă, greșeala e aproape sigur de algebră, nu de metodă.

6. Unde se poate rupe lanțul

Fiecare dintre cele două etape este obligatorie. Dacă lipsește una, „demonstrația" nu valorează nimic — și există exemple spectaculoase în ambele sensuri.

Fără verificare, pasul inductiv poate „demonstra" un fals. Ia afirmația evident greșită $Q(n)$: „$1+2+\cdots +n=\frac{n^2+n+2}{2}$" (compar-o cu formula corectă: e cu $1$ mai mare). Pasul inductiv funcționează impecabil: dacă presupunem $Q(k)$ și adunăm $k+1$, obținem

$$\frac{k^2+k+2}{2}+(k+1)=\frac{k^2+3k+4}{2}=\frac{(k+1{)}^2+(k+1)+2}{2},$$

adică exact $Q(k+1)$. Lanțul transmite perfect... doar că prima piesă nu cade niciodată: $Q(1)$ ar cere $1=\frac{4}{2}=2$, fals. Piesele sunt bine așezate, dar nimeni nu împinge prima piesă — deci nu cade niciuna.

Fără pas inductiv, verificările nu acoperă infinitatea. Este exact povestea lui $n^2+n+41$ din prima secțiune: patruzeci de verificări, zero garanții.

Morala: o inducție e completă doar cu amândouă etapele scrise negru pe alb. La barem, fiecare etapă are punctele ei.

7. Inducția care începe mai târziu: $n\ge n_0$

Nu toate afirmațiile sunt adevărate începând cu $n=1$. De exemplu, inegalitatea $2^n>2n+1$ este falsă pentru $n=1$ ($2>3$?) și pentru $n=2$ ($4>5$?), dar devine adevărată de la $n=3$ încolo ($8>7$ ✓). În astfel de situații folosim aceeași metodă, doar că prima piesă a dominoului este $P(n_0)$, nu $P(1)$:

1. verificăm $P(n_0)$;
2. demonstrăm că din $P(k)$ rezultă $P(k+1)$, pentru orice $k\ge n_0$;
3. concluzionăm că $P(n)$ este adevărată pentru orice $n\ge n_0$.

Vom exploata din plin această variantă în lecția următoare, Inducția matematică: sume, inegalități și divizibilitate, unde inegalitățile cer aproape întotdeauna un rang de pornire mai mare. Tot acolo vei vedea și cum se împacă inducția cu metoda reducerii la absurd — cele două mari metode de demonstrație ale clasei a IX-a.

Exemple rezolvate

Exemplul 1 — Suma numerelor impare

Demonstrați că pentru orice $n\ge 1$: $1+3+5+\cdots +(2n-1)=n^2$.

Rezolvare. Notăm cu $P(n)$ egalitatea din enunț (suma primelor $n$ numere impare).

Etapa de verificare. Pentru $n=1$: membrul stâng este $1$, membrul drept $1^2=1$. $P(1)$ adevărată.

Etapa de demonstrație. Presupunem $P(k)$ adevărată pentru un $k\ge 1$: $1+3+\cdots +(2k-1)=k^2$. Demonstrăm $P(k+1)$: $1+3+\cdots +(2k-1)+(2k+1)=(k+1{)}^2$. Într-adevăr, folosind ipoteza:

$$\underset{=k^2}{\underbrace{1+3+\cdots +(2k-1)}}+(2k+1)=k^2+2k+1=(k+1{)}^2.✓$$

Conform principiului inducției matematice, $P(n)$ e adevărată pentru orice $n\ge 1$. $■$

Frumusețea formulei: adunând mereu următorul număr impar, pătratele „cresc" unul din altul — de aici și desenul clasic cu pătratul din puncte completat în forma literei L.

Exemplul 2 — Suma pătratelor

Demonstrați că pentru orice $n\ge 1$: $1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$.

Rezolvare. Verificarea: pentru $n=1$, stânga este $1$, dreapta $\frac{1\cdot 2\cdot 3}{6}=1$. ✓

Demonstrația: presupunem $1^2+\cdots +k^2=\frac{k(k+1)(2k+1)}{6}$ și calculăm suma până la $k+1$:

$$\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}.$$

Descompunem trinomul: $2k^2+7k+6=(k+2)(2k+3)$ — verifici imediat prin desfacere. Deci suma este

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

exact formula pentru $n=k+1$. Conform principiului inducției, egalitatea e adevărată pentru orice $n\ge 1$. $■$

Exemplul 3 — O sumă telescopică, prin inducție

Demonstrați că pentru orice $n\ge 1$: $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots +\frac{1}{n(n+1)}=\frac{n}{n+1}$.

Rezolvare. Verificarea: $n=1$: stânga $=\frac{1}{2}$, dreapta $=\frac{1}{2}$. ✓

Demonstrația: presupunem egalitatea pentru $k$ și adunăm termenul următor:

$$\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{k^2+2k+1}{(k+1)(k+2)}=\frac{(k+1{)}^2}{(k+1)(k+2)}=\frac{k+1}{k+2}.✓$$

Aceasta este formula pentru $n=k+1$, deci, prin inducție, egalitatea are loc pentru orice $n\ge 1$. $■$

Exemplul 4 — Suma puterilor lui 2

Demonstrați că pentru orice $n\ge 1$: $1+2+2^2+\cdots +2^{n-1}=2^n-1$.

Rezolvare. Verificarea: $n=1$: stânga $=1$, dreapta $=2^1-1=1$. ✓

Demonstrația: presupunem $1+2+\cdots +2^{k-1}=2^k-1$ și adunăm $2^k$:

$$(2^k-1)+2^k=2\cdot 2^k-1=2^{k+1}-1.✓$$

Prin inducție, egalitatea e adevărată pentru orice $n\ge 1$. $■$

Formula are o interpretare practică pe care o simți imediat în informatică: cu $n$ biți poți reprezenta numerele de la $0$ la $2^n-1$ — iar suma valorilor pozițiilor $1,2,4,\dots ,2^{n-1}$ este exact $2^n-1$, cel mai mare număr reprezentabil.

Exemplul 5 — Depistează greșeala

Un elev „demonstrează" că $1+2+\cdots +n=\frac{n(n+1)}{2}+3$ astfel: „Presupun afirmația adevărată pentru $k$. Atunci suma până la $k+1$ este $\frac{k(k+1)}{2}+3+(k+1)=\frac{(k+1)(k+2)}{2}+3$, exact formula pentru $k+1$. Deci afirmația e adevărată pentru orice $n$." Unde este eroarea?

Rezolvare. Calculul din pasul inductiv este corect — poți verifica fiecare egalitate. Eroarea este lipsa etapei de verificare: pentru $n=1$, formula ar da $1=\frac{1\cdot 2}{2}+3=4$, fals. Prima piesă a dominoului nu cade, deci lanțul implicațiilor, oricât de corect, nu pornește niciodată. Concluzia elevului este falsă tocmai pentru că o inducție fără verificare nu este o demonstrație. Situația este identică cu exemplul $Q(n)$ din lecție: pasul inductiv „merge" și pentru formule greșite, dacă greșeala este o constantă adăugată — ea se simplifică la scădere și nu se vede în calcul.

Exemplul 6 — Exemplu tip Bacalaureat

Demonstrați, folosind metoda inducției matematice, că pentru orice $n\ge 1$:

$$1+4+7+\cdots +(3n-2)=\frac{n(3n-1)}{2}.$$

Rezolvare. Notăm cu $P(n)$ egalitatea din enunț; termenii din stânga formează o progresie cu pasul $3$, iar al $n$-lea termen este $3n-2$.

Etapa de verificare. $n=1$: stânga $=1$, dreapta $=\frac{1\cdot 2}{2}=1$, deci $P(1)$ e adevărată.

Etapa de demonstrație. Presupunem $P(k)$ adevărată: $1+4+\cdots +(3k-2)=\frac{k(3k-1)}{2}$. Următorul termen al sumei este $3(k+1)-2=3k+1$. Atunci:

$$\frac{k(3k-1)}{2}+(3k+1)=\frac{3k^2-k+6k+2}{2}=\frac{3k^2+5k+2}{2}=\frac{(k+1)(3k+2)}{2}=\frac{(k+1)[3(k+1)-1]}{2},$$

adică exact $P(k+1)$ — la descompunere am folosit $3k^2+5k+2=(k+1)(3k+2)$, ușor de verificat prin desfacerea parantezelor.

Concluzie. Conform principiului inducției matematice, egalitatea este adevărată pentru orice $n\ge 1$. $■$

Să exersăm

Rezolvă pe caiet, cu redactare completă — la inducție, baremul punctează separat verificarea, ipoteza, calculul și concluzia. Scrie de fiecare dată explicit cum arată $P(k+1)$ înainte de calcul.

1. Pentru $P(n)$: „$1+2+\cdots +n=\frac{n(n+1)}{2}$", verifică prin calcul direct că $P(1)$, $P(2)$ și $P(3)$ sunt adevărate.

2. Pentru $P(n)$: „$1+3+5+\cdots +(2n-1)=n^2$", scrie explicit propozițiile $P(k)$ și $P(k+1)$. Care este termenul care se adaugă la trecerea de la $P(k)$ la $P(k+1)$?

3. Demonstrează prin inducție: $1+2+3+\cdots +n=\frac{n(n+1)}{2}$, pentru orice $n\ge 1$ (redactează complet, fără să te uiți la lecție).

4. Demonstrează prin inducție: $2+4+6+\cdots +2n=n(n+1)$, pentru orice $n\ge 1$.

5. Demonstrează prin inducție: $1+3+5+\cdots +(2n-1)=n^2$, pentru orice $n\ge 1$.

6. Demonstrează prin inducție: $1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$, pentru orice $n\ge 1$.

7. (Adevărat/Fals cu motivare.) „Dacă $P(5)$ este adevărată și, pentru orice $k\ge 5$, din $P(k)$ rezultă $P(k+1)$, atunci $P(n)$ este adevărată pentru orice $n\ge 5$."

8. (Adevărat/Fals cu motivare.) „Am verificat că $P(1),P(2),\dots ,P(100)$ sunt toate adevărate; rezultă că $P(n)$ este adevărată pentru orice $n\ge 1$."

9. Demonstrează prin inducție: $1\cdot 2+2\cdot 3+\cdots +n(n+1)=\frac{n(n+1)(n+2)}{3}$, pentru orice $n\ge 1$.

10. Demonstrează prin inducție: $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots +\frac{1}{n(n+1)}=\frac{n}{n+1}$, pentru orice $n\ge 1$.

11. Un elev demonstrează pasul inductiv pentru $S(n)$: „$1+2+\cdots +n=\frac{n^2+n+2}{2}$" și susține că a terminat demonstrația. Arată printr-un calcul concret unde eșuează afirmația și explică de ce pasul inductiv singur nu este suficient.

12. Demonstrează prin inducție: $1^3+2^3+\cdots +n^3={\left[\frac{n(n+1)}{2}\right]}^2$, pentru orice $n\ge 1$. Ce legătură observi cu suma lui Gauss?

13. (Problemă aplicată.) Ana economisește după regula: în prima săptămână pune deoparte $1$ leu, iar în fiecare săptămână următoare cu $2$ lei mai mult decât în precedenta (deci $1,3,5,7,\dots$ lei). Arată, folosind inducția, că după $n$ săptămâni Ana are exact $n^2$ lei, apoi calculează după câte săptămâni depășește prima dată $400$ de lei.

14. Demonstrează prin inducție: $1+2+2^2+\cdots +2^{n-1}=2^n-1$, pentru orice $n\ge 1$.

15. (Exercițiu tip Bacalaureat.) a) Demonstrați, prin metoda inducției matematice, că $1+2+\cdots +n=\frac{n(n+1)}{2}$ pentru orice $n\ge 1$. b) Calculați $1+2+\cdots +100$.

16. Fie $P(n)$: „oricare $n$ drepte din plan, dintre care oricare două sunt concurente și oricare trei nu trec prin același punct, determină $\frac{n(n-1)}{2}$ puncte de intersecție". Verifică prin desen și numărare că $P(2)$ și $P(3)$ sunt adevărate, apoi explică de ce la trecerea de la $k$ drepte la $k+1$ drepte se adaugă exact $k$ puncte noi.

17. Demonstrează prin inducție: $1+\frac{1}{2}+\frac{1}{4}+\cdots +\frac{1}{2^n}=2-\frac{1}{2^n}$, pentru orice $n\ge 1$. Ce se întâmplă cu suma când $n$ devine foarte mare?

18. (Provocare.) În jocul „Turnurile din Hanoi", un turn de $n$ discuri se mută de pe o tijă pe alta, folosind o tijă intermediară, fără a așeza vreodată un disc mare peste unul mic. Numărul minim de mutări satisface regula: pentru un disc, $H(1)=1$, iar $H(k+1)=2H(k)+1$ (muți turnul de $k$ discuri, apoi discul mare, apoi iar turnul de $k$ discuri). Demonstrează prin inducție că $H(n)=2^n-1$.

Răspunsuri și explicații

1. $P(1)$: $1=\frac{1\cdot 2}{2}=1$ ✓. $P(2)$: $1+2=3$ și $\frac{2\cdot 3}{2}=3$ ✓. $P(3)$: $1+2+3=6$ și $\frac{3\cdot 4}{2}=6$ ✓. (Atenție: aceste verificări ilustrează, dar nu demonstrează formula pentru orice $n$.)

2. $P(k)$: $1+3+\cdots +(2k-1)=k^2$; $P(k+1)$: $1+3+\cdots +(2k-1)+(2k+1)=(k+1{)}^2$. Termenul adăugat este $2(k+1)-1=2k+1$.

3. Redactarea completă este în secțiunea 4 a lecției: verificare $P(1)$ ($1=1$), ipoteză $1+\cdots +k=\frac{k(k+1)}{2}$, calcul $\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$, concluzie prin principiul inducției.

4. Verificare: $n=1$: $2=1\cdot 2$ ✓. Pas: $\underset{=k(k+1)}{\underbrace{2+\cdots +2k}}+2(k+1)=(k+1)(k+2)$ — am scos factorul $k+1$: $k(k+1)+2(k+1)=(k+1)(k+2)$. ✓ Concluzie prin inducție.

5. Verificare: $1=1^2$ ✓. Pas: $k^2+(2k+1)=(k+1{)}^2$ ✓ (formula pătratului sumei). Concluzie prin inducție. (Este Exemplul 1, redactat de tine.)

6. Verificare: $1=\frac{1\cdot 2\cdot 3}{6}$ ✓. Pas: $\frac{k(k+1)(2k+1)}{6}+(k+1{)}^2=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$ ✓. (Descompunerea $2k^2+7k+6=(k+2)(2k+3)$.)

7. Adevărat. Este exact principiul inducției cu baza $n_0=5$: prima piesă care cade este $P(5)$, iar lanțul acoperă toate propozițiile de la rangul $5$ încolo. Despre $P(1),\dots ,P(4)$ nu putem afirma nimic.

8. Fals. Oricâte cazuri particulare nu demonstrează o afirmație despre toate numerele naturale — contraexemplul $n^2+n+41$ trece de $40$ de verificări și pică la a $41$-a. Fără pasul inductiv, lanțul nu există.

9. Verificare: $1\cdot 2=2$ și $\frac{1\cdot 2\cdot 3}{3}=2$ ✓. Pas: $\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=(k+1)(k+2)\left(\frac{k}{3}+1\right)=\frac{(k+1)(k+2)(k+3)}{3}$ ✓. Concluzie prin inducție.

10. Verificare: $\frac{1}{2}=\frac{1}{2}$ ✓. Pas: $\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1{)}^2}{(k+1)(k+2)}=\frac{k+1}{k+2}$ ✓. (Este Exemplul 3.)

11. Pentru $n=1$ formula dă $1=\frac{1+1+2}{2}=2$, fals — deci afirmația pică la verificare. Pasul inductiv este totuși corect (constanta greșită se „transmite" fără să se vadă), ceea ce arată că pasul inductiv fără verificare poate susține și formule false: lanțul e bine construit, dar prima piesă nu cade.

12. Verificare: $1^3=1$ și ${\left[\frac{1\cdot 2}{2}\right]}^2=1$ ✓. Pas: ${\left[\frac{k(k+1)}{2}\right]}^2+(k+1{)}^3=(k+1{)}^2\left[\frac{k^2}{4}+(k+1)\right]=(k+1{)}^2\cdot \frac{k^2+4k+4}{4}={\left[\frac{(k+1)(k+2)}{2}\right]}^2$ ✓. Legătura: suma cuburilor este exact pătratul sumei lui Gauss: $1^3+\cdots +n^3=(1+2+\cdots +n{)}^2$.

13. Sumele de bani sunt $1+3+5+\cdots +(2n-1)$, adică suma primelor $n$ numere impare; prin inducția de la exercițiul 5, totalul este $n^2$ lei. Cerința finală: căutăm cel mai mic $n$ cu $n^2>400$, adică $n>20$; după $n=21$ de săptămâni Ana are $441>400$ de lei (după $20$ are exact $400$, care nu „depășește").

14. Verificare: $1=2^1-1$ ✓. Pas: $(2^k-1)+2^k=2^{k+1}-1$ ✓. Concluzie prin inducție. (Este Exemplul 4.)

15. a) Demonstrația de la exercițiul 3. b) $\frac{100\cdot 101}{2}=5050$. (Anecdota spune că micul Gauss a calculat această sumă în câteva secunde, grupând $1+100=2+99=\cdots =101$, de $50$ de ori.)

16. $P(2)$: două drepte concurente au $1=\frac{2\cdot 1}{2}$ punct ✓. $P(3)$: trei drepte, oricare două concurente și fără punct comun triplu, dau $3=\frac{3\cdot 2}{2}$ puncte ✓. La adăugarea dreptei $k+1$: ea taie fiecare dintre cele $k$ drepte existente în câte un punct, iar aceste puncte sunt distincte (altfel trei drepte ar fi concurente) — deci apar exact $k$ puncte noi: $\frac{k(k-1)}{2}+k=\frac{k(k+1)}{2}$, adică formula pentru $k+1$ drepte.

17. Verificare: $n=1$: $1+\frac{1}{2}=\frac{3}{2}$ și $2-\frac{1}{2}=\frac{3}{2}$ ✓. Pas: $\left(2-\frac{1}{2^k}\right)+\frac{1}{2^{k+1}}=2-\frac{2}{2^{k+1}}+\frac{1}{2^{k+1}}=2-\frac{1}{2^{k+1}}$ ✓. Când $n$ crește, $\frac{1}{2^n}$ devine oricât de mic, deci suma se apropie oricât de mult de $2$, fără să-l atingă — prima ta întâlnire cu ideea de limită.

18. Verificare: $H(1)=1=2^1-1$ ✓. Pas: presupunem $H(k)=2^k-1$; atunci $H(k+1)=2H(k)+1=2(2^k-1)+1=2^{k+1}-2+1=2^{k+1}-1$ ✓. Prin inducție, $H(n)=2^n-1$ pentru orice $n\ge 1$. Pentru legenda cu $64$ de discuri, călugării ar avea nevoie de $2^{64}-1\approx 1,8\cdot 10^{19}$ mutări — la o mutare pe secundă, de sute de ori vârsta universului.

De reținut

• Verificarea unor cazuri particulare nu este demonstrație — contraexemplul $n^2+n+41$ trece de $40$ de teste și apoi pică. Cazurile particulare doar sugerează; inducția demonstrează.
• Principiul inducției matematice: dacă $P(1)$ este adevărată și din $P(k)$ rezultă $P(k+1)$ pentru orice $k\ge 1$, atunci $P(n)$ este adevărată pentru orice $n\ge 1$ — principiul dominoului.
• O demonstrație prin inducție are două etape obligatorii: etapa de verificare ($P(1)$, prin calcul direct) și etapa de demonstrație (din ipoteza de inducție $P(k)$ deducem $P(k+1)$), încheiate cu concluzia.
• În pasul inductiv nu presupui concluzia: presupui o singură verigă, $P(k)$, și arăți că adevărul se transmite la $P(k+1)$. La sume, tehnica standard: rupi suma până la $k+1$ în „suma până la $k$" (din ipoteză) plus ultimul termen.
• Dacă afirmația e adevărată doar de la un rang încolo, inducția pornește de la $n_0$: verifici $P(n_0)$ și transmiți pentru $k\ge n_0$.

Greșeli frecvente

• Lipsa etapei de verificare. Pasul inductiv poate „funcționa" și pentru formule false (greșite cu o constantă) — fără $P(1)$ verificat, demonstrația nu valorează nimic. Baremul dă puncte separat pe verificare tocmai de aceea.
• „Presupunem că $P(n)$ e adevărată pentru orice $n$…" — formulare fatală: ai presupus chiar concluzia. Corect: „presupunem $P(k)$ adevărată pentru un $k\ge 1$ fixat".
• Nu scrii ținta. Dacă nu notezi explicit cum arată $P(k+1)$, calculezi „în orb" și nu știi când să te oprești. Scrie ținta înainte de calcul și compară la final.
• Uiți termenul de legătură. La trecerea de la $k$ la $k+1$, în sumă se adaugă exact termenul de rang $k+1$ — de exemplu $2k+1$ la suma imparelor, $3k+1$ la suma din Exemplul 6. Calculează-l separat, înainte de a-l aduna.
• Verificarea făcută pentru $n$ greșit. La afirmații valabile pentru $n\ge n_0$ (de exemplu inegalități), verificarea se face pentru $n_0$, nu pentru $1$ — altfel „demonstrezi" pornind de la un caz fals.

Aplică acasă

1. Dominoul real. Așază pe masă 8–10 piese de domino (sau cărți de joc îndoite) și declanșează lanțul. Apoi scoate o piesă din mijloc și declanșează din nou. Ce propoziții $P(n)$ „cad" acum? Leagă experimentul de ce se întâmplă când pasul inductiv eșuează la un anumit $k$.

2. Suma lui Gauss pe bonuri. Ia un bon de cumpărături cu cel puțin 6 produse și numerotează-le $1,2,\dots ,n$. Verifică formula $1+2+\cdots +n=\frac{n(n+1)}{2}$ pentru $n$-ul tău, apoi calculează cu formula câte strângeri de mână au loc într-o clasă cu 25 de elevi dacă fiecare dă mâna cu fiecare o singură dată (răspuns: $\frac{24\cdot 25}{2}=300$).

3. Foaia îndoită. Îndoaie o foaie A4 în două, apoi iar în două și tot așa, de câte ori poți (practic 6–7 îndoiri). După $n$ îndoiri, foaia are $2^n$ straturi — verifică pentru primele 3 îndoiri numărând straturile, apoi folosește formula din Exemplul 4 ca să afli câte straturi ar avea foaia după 42 de îndoiri ($2^{42}$, o grosime cât distanța Pământ–Lună la o foaie de $0,1$ mm).

Pentru părinți și profesori

Această lecție deschide, împreună cu Metoda reducerii la absurd, capitolul metodelor de demonstrație — diferența specifică a programei de matematică-informatică față de trunchiul comun. Inducția matematică este prima întâlnire a elevului cu o demonstrație „despre infinit" și cu ideea, fundamentală în informatică, de recursivitate: exact același mecanism prin care o funcție recursivă corectă are un caz de bază și un pas care reduce problema.

Punctele de verificat în redactarea elevului: (1) scrie explicit afirmația $P(n)$; (2) face verificarea pentru rangul de pornire corect; (3) formulează ipoteza „pentru un $k$ fixat", nu „pentru orice $n$"; (4) scrie ținta $P(k+1)$ înainte de calcul; (5) încheie cu concluzia standard. Întrebări bune de control: „De ce nu ajunge că formula merge pentru primele 100 de numere?" (contraexemplul $n^2+n+41$); „Ce s-ar întâmpla dacă am sări verificarea?" (Exemplul 5); „Care este termenul care se adaugă la trecerea de la $k$ la $k+1$?".

La Bacalaureat (M1, mate-info), inducția apare la subiectul de algebră fie direct („demonstrați prin inducție…"), fie mascat în probleme cu șiruri și sume; redactarea celor două etape aduce punctaj chiar și atunci când calculul final scapă. Semne că elevul a înțeles: poate explica analogia dominoului cu propriile cuvinte, depistează singur greșeala din Exemplul 5 și nu confundă ipoteza de inducție cu concluzia.

Întrebări frecvente

Ce este metoda inducției matematice, pe scurt? Este o metodă de a demonstra că o afirmație $P(n)$ este adevărată pentru toate numerele naturale $n\ge 1$, în două etape: arăți că $P(1)$ este adevărată (verificarea) și că din $P(k)$ rezultă mereu $P(k+1)$ (pasul inductiv). Ca la domino: prima piesă cade și fiecare piesă o dărâmă pe următoarea, deci cad toate.

De ce nu pot demonstra o formulă verificând multe cazuri? Pentru că oricâte cazuri verifici, rămân infinite cazuri neverificate — și există exemple celebre care merg zeci de cazuri și apoi pică, precum $n^2+n+41$, prim pentru $n=0,1,\dots ,39$, dar egal cu $41^2$ pentru $n=40$. Verificările pot doar sugera sau infirma, nu demonstra.

Care sunt cele două etape ale inducției matematice? Etapa de verificare: arăți prin calcul direct că afirmația e adevărată pentru primul rang (de regulă $n=1$). Etapa de demonstrație (pasul inductiv): presupui afirmația adevărată pentru un $k$ fixat (ipoteza de inducție) și demonstrezi că rezultă și pentru $k+1$. Ambele sunt obligatorii.

Ce este ipoteza de inducție? Este presupunerea, făcută în pasul inductiv, că $P(k)$ este adevărată pentru un anumit $k$ fixat. Nu presupui concluzia (adevărul pentru toate numerele), ci doar o verigă a lanțului, pe care o folosești ca să demonstrezi veriga următoare, $P(k+1)$.

Ce se întâmplă dacă sar etapa de verificare? Poți „demonstra" lucruri false. Există formule greșite (de exemplu corecte plus o constantă) pentru care pasul inductiv funcționează perfect, dar care pică la $n=1$. Fără prima piesă împinsă, dominoul nu pornește — de aceea baremul punctează separat verificarea.

Pot folosi inducția dacă afirmația e adevărată doar de la un anumit număr încolo? Da. Dacă afirmația e adevărată doar pentru $n\ge n_0$, verifici $P(n_0)$ în loc de $P(1)$ și demonstrezi transmiterea $P(k)\Rightarrow P(k+1)$ pentru $k\ge n_0$. Concluzia acoperă toate numerele de la $n_0$ încolo — util mai ales la inegalități.

Unde apare inducția matematică la Bacalaureat? La proba M1 (mate-info), în subiectele de algebră: demonstrarea unor identități cu sume, proprietăți ale șirurilor definite prin recurență, iar mai târziu la puteri de matrice. Chiar și când nu se cere explicit „prin inducție", metoda este adesea calea naturală de rezolvare.

Ce legătură are inducția cu informatica? Aceeași structură stă la baza recursivității: o funcție recursivă corectă are un caz de bază (verificarea) și un apel care reduce problema la una mai mică (pasul inductiv). Demonstrarea corectitudinii unui algoritm recursiv se face, riguros, chiar prin inducție matematică.