Moduri de definire a unui șir; șiruri date prin recurență

Există două feluri de a-i spune cuiva unde locuiești. Primul: „strada Alba, numărul 47" — informația completă, dintr-o singură propoziție, oricine ajunge direct la ușă. Al doilea: „pornești de la primărie, mergi până la a treia intersecție, apoi la fiecare colț faci dreapta" — o instrucțiune care nu-ți spune direct adresa, dar te duce acolo, pas cu pas. Ambele descriu perfect același loc, doar că unul îl numește, iar celălalt îl construiește.

Șirurile de numere se definesc exact în aceste două feluri. Uneori primești formula termenului general, $a_{n} = 3 n - 1$ , și poți afla instantaneu al o mie-lea termen. Alteori primești o regulă de trecere de la un termen la următorul — „pornești de la $1$ și dublezi mereu, adăugând $3$ " — și trebuie să parcurgi drumul. A doua formă se numește definire prin recurență și este limbajul natural al informaticii: orice funcție recursivă, orice buclă care își actualizează o variabilă, orice proces care evoluează în timp se scrie așa. În lecția aceasta vedem toate modurile de a defini un șir, învățăm să trecem de la unul la altul și punem inducția matematică la treabă acolo unde trecerea trebuie demonstrată.

Ce vei învăța

Vei ști să definești riguros noțiunea de șir de numere reale ca funcție definită pe mulțimea numerelor naturale și să folosești corect termenii „rang" și „termen".
Vei ști să recunoști și să folosești cele trei moduri de definire: prin descriere, prin formula termenului general și prin relație de recurență.
Vei ști să calculezi termenii unui șir dat printr-o relație de recurență, cu unul sau cu doi termeni de pornire.
Vei ști să treci de la o recurență la formula explicită în cazurile clasice și să demonstrezi corectitudinea formulei prin inducție matematică.
Vei ști să scrii progresiile aritmetice și geometrice ca șiruri recurente și să recunoști aceste recurențe în probleme practice.
Vei ști să lucrezi cu șirul lui Fibonacci și să înțelegi de ce o recurență de ordinul al doilea are nevoie de doi termeni de pornire.

Hai să descoperim împreună

1. Ce este, riguros, un șir

Definiție. Se numește șir de numere reale orice funcție $f : N^{*} \to R$ . Valoarea $f (n)$ se notează cu $a_{n}$ și se numește termenul de rang $n$ al șirului, iar șirul însuși se notează $(a_{n})_{n \geq 1}$ .

Notația cu indice nu este un capriciu: ea subliniază că ne interesează ordinea. Un șir nu este o mulțime de numere, ci o listă ordonată, în care fiecare număr are un loc precis. Șirurile $1, 2, 3$ și $3, 2, 1$ au aceiași termeni ca mulțimi, dar sunt șiruri diferite. Și, spre deosebire de o mulțime, un șir poate repeta valori: $1, 1, 1, \dots$ este un șir perfect valid, cu o infinitate de termeni toți egali cu $1$ .

Uneori e mai comod să numerotăm de la $0$ ; atunci vorbim de un șir $(a_{n})_{n \geq 0}$ , funcție definită pe $N$ . Alegerea e o convenție, dar trebuie păstrată consecvent în toată problema — multe greșeli de exponent vin din schimbarea ei pe parcurs. Noțiunile de bază, termen și rang, le-ai întâlnit deja în lecția Șiruri: termen, rang, formula termenului general; aici mergem mai departe, spre modurile de definire.

2. Definirea prin descriere

Cel mai simplu — și cel mai puțin precis — mod de a defini un șir este să spui în cuvinte ce reprezintă termenii lui:

$a_{n}$ = al $n$ -lea număr prim: $2, 3, 5, 7, 11, 13, 17, 19, \dots$
$a_{n}$ = numărul de divizori naturali ai lui $n$ : $1, 2, 2, 3, 2, 4, \dots$
$a_{n}$ = a $n$ -a zecimală a numărului $π$ : $1, 4, 1, 5, 9, 2, \dots$

Definiția este corectă — fiecare termen e determinat fără ambiguitate — dar nu ne dă niciun mijloc de calcul rapid. Pentru șirul numerelor prime nu există (și, se crede, nu poate exista) o formulă simplă care să dea direct al $n$ -lea termen; ca să afli al $100$ -lea număr prim, trebuie să le găsești pe toate cele dinainte.

Atenție la o capcană frecventă: enumerarea câtorva termeni nu este o definiție. Dacă scriu „ $2, 4, 8, \dots$ ", continuarea poate fi $16$ , dacă regula este „dublează mereu"; dar poate fi la fel de bine $14$ , dacă regula este „adaugă de fiecare dată un număr par cu $2$ mai mare decât precedentul", care produce $2, 4, 8, 14, 22$ . Punctele de suspensie sunt o sugestie, nu o definiție. De aceea, la un exercițiu care cere „continuați șirul", răspunsul corect include întotdeauna regula pe care ai presupus-o.

3. Definirea prin formula termenului general

Aceasta este forma „adresa completă": o expresie care, pentru orice rang $n$ , dă direct termenul.

$a_{n} = 3 n - 1 ⟹ 2, 5, 8, 11, 14, 17, \dots$ $b_{n} = n^{2} + 1 ⟹ 2, 5, 10, 17, 26, \dots$ $c_{n} = (- 1)^{n} \cdot n ⟹ - 1, 2, - 3, 4, - 5, \dots$ $d_{n} = \frac{1}{n ( n + 1 )} ⟹ \frac{1}{2}, \frac{1}{6}, \frac{1}{12}, \frac{1}{20}, \dots$

Avantajul e evident: pentru $a_{n} = 3 n - 1$ , termenul de rang $1000$ se află dintr-o singură înmulțire, $a_{1000} = 2999$ . Tot de aici rezolvi și problema inversă, aflarea rangului: dacă știm că un termen este $59$ , rezolvăm ecuația $3 n - 1 = 59$ , deci $n = 20$ — al douăzecilea termen. Reține că rangul trebuie să iasă număr natural; dacă ecuația dă $n = 7, 5$ , concluzia este că valoarea respectivă nu apare în șir.

Factorul $(- 1)^{n}$ merită reținut ca truc: el este $- 1$ pentru $n$ impar și $+ 1$ pentru $n$ par, deci produce alternanța semnelor. La fel, $(- 1)^{n + 1}$ inversează alternanța.

4. Definirea prin recurență

A treia formă — și cea mai importantă la mate-info — dă regula de trecere de la un termen la următorul, plus punctul de plecare. O astfel de definiție are întotdeauna două părți:

${a_{1} = valoarea de pornire, a_{n + 1} = expresie \overset{ı}{ˆ} n a_{n} (ș i eventual \overset{ı}{ˆ} n n), n \geq 1.$

Ambele părți sunt indispensabile. Fără regulă nu știi cum să continui; fără termenul de pornire, regula descrie o infinitate de șiruri diferite. Recurența $a_{n + 1} = 2 a_{n}$ este satisfăcută și de $1, 2, 4, 8, \dots$ , și de $5, 10, 20, 40, \dots$ , și de $- 3, - 6, - 12, \dots$ — abia primul termen alege unul dintre ele.

Să calculăm termenii pentru trei recurențe:

(i) $a_{1} = 2$ , $a_{n + 1} = a_{n} + 5$ : obținem $2, 7, 12, 17, 22, \dots$ — recunoști o progresie aritmetică.

(ii) $a_{1} = 3$ , $a_{n + 1} = 2 a_{n}$ : obținem $3, 6, 12, 24, 48, \dots$ — o progresie geometrică.

(iii) $a_{1} = 1$ , $a_{n + 1} = 2 a_{n} + 3$ : obținem $1, 5, 13, 29, 61, 125, \dots$ — nici aritmetică (diferențele sunt $4, 8, 16, 32$ ), nici geometrică (rapoartele sunt $5; 2, 6; 2, 23 \dots$ ).

Primele două exemple arată un lucru important: progresiile sunt cazuri particulare de șiruri recurente. Progresia aritmetică este exact șirul definit de $a_{n + 1} = a_{n} + r$ , iar cea geometrică de $b_{n + 1} = b_{n} \cdot q$ — definițiile din lecțiile Progresia aritmetică și rația și Progresia geometrică și rația sunt, citite corect, relații de recurență. Așa apar ele și în practică: dobânda compusă înseamnă $C_{n + 1} = C_{n} \cdot 1, 05$ , adică „suma de anul viitor = suma de anul acesta înmulțită cu $1, 05$ ", ca în lecția Dobânda compusă și dinamica populației.

Recurența poate depinde și de rang, nu doar de termenul precedent. De exemplu, $a_{1} = 1$ și $a_{n + 1} = a_{n} + n$ dau $1, 2, 4, 7, 11, 16, 22, \dots$ : la fiecare pas se adaugă altceva, anume rangul curent.

5. De la recurență la formula explicită

Definirea prin recurență e comodă de scris, dar incomodă de folosit: ca să afli $a_{100}$ trebuie să calculezi toți cei $99$ de termeni dinainte. De aceea, ori de câte ori se poate, căutăm formula explicită a termenului general.

Să luăm recurența (iii): $a_{1} = 1$ , $a_{n + 1} = 2 a_{n} + 3$ . Scriem termenii și le căutăm tiparul:

$1, 5, 13, 29, 61, 125, \dots$

Nimic evident. Dar dacă adunăm $3$ la fiecare:

$4, 8, 16, 32, 64, 128, \dots$

— puterile lui $2$ ! Aceasta sugerează substituția $b_{n} = a_{n} + 3$ . Verificăm că ea transformă recurența într-una simplă:

$b_{n + 1} = a_{n + 1} + 3 = (2 a_{n} + 3) + 3 = 2 a_{n} + 6 = 2 (a_{n} + 3) = 2 b_{n} .$

Deci $(b_{n})$ este o progresie geometrică de rație $2$ , cu $b_{1} = a_{1} + 3 = 4$ . Termenul ei general este $b_{n} = 4 \cdot 2^{n - 1} = 2^{n + 1}$ , de unde

$a_{n} = b_{n} - 3 = 2^{n + 1} - 3.$

Verificăm pe primii termeni: $n = 1$ dă $4 - 3 = 1$ ✓; $n = 3$ dă $16 - 3 = 13$ ✓; $n = 5$ dă $64 - 3 = 61$ ✓.

Aici trebuie făcută o distincție de rigoare, esențială la mate-info. Substituția de mai sus a fost ghicită privind numerele; verificarea pe câțiva termeni nu demonstrează nimic, așa cum ai văzut în lecția Metoda inducției matematice. Formula găsită trebuie demonstrată, iar instrumentul potrivit este chiar inducția:

Etapa de verificare: pentru $n = 1$ , formula dă $2^{2} - 3 = 1 = a_{1}$ ✓.

Etapa de demonstrație: presupunem $a_{k} = 2^{k + 1} - 3$ pentru un $k \geq 1$ . Atunci, folosind recurența,

$a_{k + 1} = 2 a_{k} + 3 = 2 (2^{k + 1} - 3) + 3 = 2^{k + 2} - 6 + 3 = 2^{k + 2} - 3,$

adică exact formula pentru rangul $k + 1$ . Prin inducție, $a_{n} = 2^{n + 1} - 3$ pentru orice $n \geq 1$ . $■$

Reține tiparul de lucru, valabil aproape întotdeauna: calculezi termeni → conjecturezi formula → demonstrezi prin inducție. Recurența îți dă exact ce-ți trebuie în pasul inductiv, pentru că leagă $a_{k + 1}$ de $a_{k}$ .

6. Recurențe de ordinul al doilea: șirul lui Fibonacci

Nu orice recurență se sprijină doar pe termenul precedent. Cea mai celebră din matematică leagă fiecare termen de doi termeni dinainte:

$F_{1} = 1, F_{2} = 1, F_{n + 2} = F_{n + 1} + F_{n}, n \geq 1.$

Obținem șirul lui Fibonacci: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$ Fiecare termen este suma celor doi dinaintea lui.

Observă de ce sunt necesari doi termeni de pornire: regula are nevoie de două valori anterioare, deci un singur termen dat nu e suficient ca să pornească lanțul. În general, o recurență care folosește $k$ termeni anteriori are nevoie de $k$ valori de pornire.

Șirul lui Fibonacci nu este progresie geometrică: rapoartele termenilor consecutivi sunt $1; 2; 1, 5; 1, 667; 1, 6; 1, 625; \dots$ — se apropie de un număr celebru, secțiunea de aur $φ \approx 1, 618$ , dar nu sunt egale. Este un exemplu bun de șir a cărui recurență e foarte simplă, dar a cărui formulă explicită e complicată (o vei întâlni în liceu, sub numele de formula lui Binet).

Fibonacci are și proprietăți frumoase, demonstrabile exact cu unealta din lecția Inducția matematică: sume, inegalități și divizibilitate. De exemplu, suma primilor $n$ termeni este $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ : pentru $n = 5$ , suma $1 + 1 + 2 + 3 + 5 = 12$ , iar $F_{7} - 1 = 13 - 1 = 12$ ✓.

7. Cum alegi forma potrivită

Cele trei moduri de definire nu sunt concurente, ci complementare — fiecare e bun la altceva:

Modul de definire	Bun pentru	Slab la
descriere	a spune ce reprezintă termenii	calcul efectiv
formula termenului general	calculul unui termen de rang mare, aflarea rangului	a surprinde un proces pas cu pas
recurență	modelarea unui proces care evoluează, programare	calculul unui termen îndepărtat

În probleme practice, modelul apare aproape întotdeauna sub formă recurentă — „populația de anul viitor = populația de anul acesta ori $1, 02$ " — pentru că așa funcționează fenomenul. Sarcina matematicianului este apoi să găsească formula explicită, ca să poată răspunde la întrebări de tipul „ce se întâmplă peste $50$ de ani" fără să parcurgă toți pașii. Acest du-te-vino între cele două forme este una dintre deprinderile de bază ale clasei a IX-a la mate-info.

Exemple rezolvate

Exemplul 1 — De la formulă la termeni și la rang

Se consideră șirul $(a_{n})_{n \geq 1}$ cu $a_{n} = \frac{2 n - 1}{n + 1}$ . a) Calculați $a_{1}$ , $a_{3}$ și $a_{10}$ . b) Arătați că toți termenii șirului sunt mai mici decât $2$ .

Rezolvare. a) Înlocuim direct: $a_{1} = \frac{1}{2}$ , $a_{3} = \frac{5}{4}$ , $a_{10} = \frac{19}{11}$ .

b) Inegalitatea $\frac{2 n - 1}{n + 1} < 2$ este echivalentă (numitorul $n + 1$ fiind pozitiv) cu $2 n - 1 < 2 (n + 1)$ , adică $2 n - 1 < 2 n + 2$ , adică $- 1 < 2$ — adevărat pentru orice $n$ . Deci toți termenii sunt mai mici decât $2$ . $■$

Exemplul 2 — Trei recurențe, primii termeni

Calculați primii cinci termeni pentru: a) $a_{1} = 2$ , $a_{n + 1} = a_{n} + 5$ ; b) $b_{1} = 1$ , $b_{n + 1} = b_{n} + 2 n + 1$ ; c) $c_{1} = 1$ , $c_{n + 1} = \frac{c _{n}}{1 + c _{n}}$ .

Rezolvare. a) $2$ ; $2 + 5 = 7$ ; $12$ ; $17$ ; $22$ . Este o progresie aritmetică de rație $5$ .

b) $1$ ; $1 + 2 \cdot 1 + 1 = 4$ ; $4 + 2 \cdot 2 + 1 = 9$ ; $9 + 2 \cdot 3 + 1 = 16$ ; $16 + 2 \cdot 4 + 1 = 25$ . Sunt pătratele perfecte: $b_{n} = n^{2}$ — firesc, pentru că $n^{2} + (2 n + 1) = (n + 1)^{2}$ .

c) $1$ ; $\frac{1}{1 + 1} = \frac{1}{2}$ ; $\frac{1/2}{1 + 1/2} = \frac{1/2}{3/2} = \frac{1}{3}$ ; analog $\frac{1}{4}$ ; $\frac{1}{5}$ . Conjectura $c_{n} = \frac{1}{n}$ se verifică imediat prin inducție: dacă $c_{k} = \frac{1}{k}$ , atunci $c_{k + 1} = \frac{1/ k}{1 + 1/ k} = \frac{1/ k}{( k + 1 ) / k} = \frac{1}{k + 1}$ . ✓

Exemplul 3 — Progresiile, scrise recurent

Scrieți sub formă de recurență: a) progresia aritmetică cu $a_{1} = 5$ și rația $3$ ; b) progresia geometrică cu $b_{1} = 2$ și rația $4$ . Apoi scrieți formulele explicite.

Rezolvare. a) Recurența: $a_{1} = 5$ , $a_{n + 1} = a_{n} + 3$ . Termenii: $5, 8, 11, 14, \dots$ , iar formula explicită este $a_{n} = 5 + 3 (n - 1) = 3 n + 2$ .

b) Recurența: $b_{1} = 2$ , $b_{n + 1} = 4 b_{n}$ . Termenii: $2, 8, 32, 128, \dots$ , iar formula explicită este $b_{n} = 2 \cdot 4^{n - 1}$ .

Observă structura: recurența spune ce se întâmplă la un pas, formula explicită spune unde ajungi după $n - 1$ pași. Trecerea de la una la alta e chiar deducerea termenului general al progresiei.

Exemplul 4 — De la recurență la formulă, prin substituție

Se consideră șirul $a_{1} = 2$ , $a_{n + 1} = 3 a_{n} - 2$ . a) Calculați primii cinci termeni. b) Arătați că șirul $b_{n} = a_{n} - 1$ este o progresie geometrică și deduceți formula lui $a_{n}$ .

Rezolvare. a) $2$ ; $3 \cdot 2 - 2 = 4$ ; $3 \cdot 4 - 2 = 10$ ; $28$ ; $82$ .

b) Calculăm raportul folosind recurența:

$b_{n + 1} = a_{n + 1} - 1 = (3 a_{n} - 2) - 1 = 3 a_{n} - 3 = 3 (a_{n} - 1) = 3 b_{n} .$

Deci $(b_{n})$ este progresie geometrică de rație $3$ , cu $b_{1} = a_{1} - 1 = 1$ . Rezultă $b_{n} = 3^{n - 1}$ și, prin urmare,

$a_{n} = 3^{n - 1} + 1.$

Verificare: $n = 4$ dă $27 + 1 = 28$ ✓. (Riguros, formula se confirmă prin inducție: dacă $a_{k} = 3^{k - 1} + 1$ , atunci $a_{k + 1} = 3 (3^{k - 1} + 1) - 2 = 3^{k} + 1$ ✓.)

Cum se ghicește substituția? Se caută numărul $t$ pentru care $a_{n + 1} - t = 3 (a_{n} - t)$ ; desfăcând, $a_{n + 1} = 3 a_{n} - 2 t$ , deci $2 t = 2$ și $t = 1$ .

Exemplul 5 — Fibonacci și suma lui

Pentru șirul lui Fibonacci, calculați primii zece termeni și verificați relația $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ pentru $n = 6$ . Demonstrați apoi relația prin inducție.

Rezolvare. Termenii: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55$ . Pentru $n = 6$ : suma este $1 + 1 + 2 + 3 + 5 + 8 = 20$ , iar $F_{8} - 1 = 21 - 1 = 20$ ✓.

Demonstrația. Notăm cu $P (n)$ relația din enunț.

Verificare: $n = 1$ : stânga $= F_{1} = 1$ , dreapta $= F_{3} - 1 = 2 - 1 = 1$ ✓.

Pasul inductiv: presupunem $F_{1} + \dots + F_{k} = F_{k + 2} - 1$ . Adăugăm termenul următor și folosim chiar recurența lui Fibonacci:

$= F_{k + 2} - 1 F_{1} + \dots + F_{k} + F_{k + 1} = F_{k + 2} + F_{k + 1} - 1 = F_{k + 3} - 1,$

adică exact $P (k + 1)$ . Conform principiului inducției matematice, relația e adevărată pentru orice $n \geq 1$ . $■$

Exemplul 6 — Exemplu tip Bacalaureat

Se consideră șirul $(a_{n})_{n \geq 1}$ definit prin $a_{1} = 1$ și $a_{n + 1} = 2 a_{n} + 3$ , pentru orice $n \geq 1$ . a) Calculați $a_{2}$ , $a_{3}$ și $a_{4}$ . b) Demonstrați că $a_{n} = 2^{n + 1} - 3$ , pentru orice $n \geq 1$ .

Rezolvare. a) $a_{2} = 2 \cdot 1 + 3 = 5$ ; $a_{3} = 2 \cdot 5 + 3 = 13$ ; $a_{4} = 2 \cdot 13 + 3 = 29$ .

b) Demonstrăm prin inducție. Notăm cu $P (n)$ afirmația „ $a_{n} = 2^{n + 1} - 3$ ".

Etapa de verificare. Pentru $n = 1$ : $2^{2} - 3 = 4 - 3 = 1 = a_{1}$ , deci $P (1)$ este adevărată.

Etapa de demonstrație. Presupunem $P (k)$ adevărată pentru un $k \geq 1$ , adică $a_{k} = 2^{k + 1} - 3$ . Folosind relația de recurență:

$a_{k + 1} = 2 a_{k} + 3 = 2 (2^{k + 1} - 3) + 3 = 2^{k + 2} - 6 + 3 = 2^{k + 2} - 3 = 2^{(k + 1) + 1} - 3,$

adică exact $P (k + 1)$ .

Concluzie. Conform principiului inducției matematice, $a_{n} = 2^{n + 1} - 3$ pentru orice $n \geq 1$ . $■$

Să exersăm

Rezolvă pe caiet. La orice conjectură dedusă din primii termeni, adaugă demonstrația prin inducție — la mate-info, „am verificat pe primii patru termeni" nu este o justificare acceptată.

1. Scrie primii cinci termeni pentru: a) $a_{n} = 3 n - 1$ ; b) $a_{n} = n^{2} + 1$ ; c) $a_{n} = (- 1)^{n} \cdot n$ ; d) $a_{n} = \frac{1}{n ( n + 1 )}$ .

2. Pentru șirul $a_{n} = 3 n - 1$ , determină rangul termenului egal cu $59$ . Arată apoi că $100$ nu este termen al șirului.

3. Calculează primii cinci termeni ai șirului $a_{1} = 2$ , $a_{n + 1} = a_{n} + 5$ . Ce fel de progresie este și care e rația?

4. Calculează primii cinci termeni ai șirului $a_{1} = 3$ , $a_{n + 1} = 2 a_{n}$ . Scrie formula explicită a termenului general.

5. Calculează primii cinci termeni ai șirului $a_{1} = 1$ , $a_{n + 1} = 2 a_{n} + 3$ , apoi arată prin ambele teste că șirul nu este nici progresie aritmetică, nici geometrică.

6. (Adevărat/Fals cu motivare.) „O relație de recurență determină complet șirul, chiar dacă nu se precizează primul termen."

7. (Adevărat/Fals cu motivare.) „Șirul lui Fibonacci este o progresie geometrică, pentru că raportul termenilor consecutivi se apropie de $1, 618$ ."

8. Scrie primii zece termeni ai șirului lui Fibonacci și calculează rapoartele $\frac{F _{n + 1}}{F _{n}}$ pentru $n = 1, \dots, 6$ , rotunjite la trei zecimale.

9. Se dă $a_{1} = 1$ , $a_{n + 1} = a_{n} + n$ . Calculează primii șase termeni și arată că $a_{n} = 1 + \frac{n ( n - 1 )}{2}$ , pentru orice $n \geq 1$ .

10. Se dă $a_{1} = 1$ , $a_{n + 1} = \frac{a _{n}}{1 + a _{n}}$ . Calculează primii patru termeni, formulează o conjectură pentru $a_{n}$ și demonstreaz-o prin inducție.

11. (Problemă aplicată.) Un depozit de $2000$ de lei crește cu $5%$ pe an. Scrie relația de recurență care leagă suma din anul $n + 1$ de suma din anul $n$ , apoi formula explicită a lui $C_{n}$ , cu $C_{0} = 2000$ .

12. Se dă $a_{1} = 2$ , $a_{n + 1} = 3 a_{n} - 2$ . Arată că $b_{n} = a_{n} - 1$ este progresie geometrică și deduce formula lui $a_{n}$ .

13. Explică de ce șirul numerelor prime se poate defini descriptiv, dar nu printr-o formulă simplă a termenului general. Ce ai avea de făcut, practic, ca să afli al $50$ -lea termen?

14. Scrie sub formă de recurență: a) progresia aritmetică cu $a_{1} = 7$ și rația $- 4$ ; b) progresia geometrică cu $b_{1} = 5$ și rația $\frac{1}{2}$ . Dă și formulele explicite.

15. (Exercițiu tip Bacalaureat.) Se consideră șirul $(a_{n})_{n \geq 1}$ cu $a_{1} = 1$ și $a_{n + 1} = 2 a_{n} + 3$ . a) Calculați $a_{2}$ , $a_{3}$ , $a_{4}$ . b) Demonstrați că $a_{n} = 2^{n + 1} - 3$ pentru orice $n \geq 1$ .

16. Pentru șirul $a_{n} = \frac{2 n - 1}{n + 1}$ , calculează $a_{1}$ , $a_{5}$ , $a_{10}$ și arată că toți termenii sunt strict mai mici decât $2$ .

17. Se dă $a_{1} = 1$ și $a_{n + 1} = a_{n} + 2 n + 1$ . Calculează primii cinci termeni, recunoaște șirul și demonstrează formula găsită prin inducție.

18. (Provocare.) Pentru șirul lui Fibonacci, demonstrează prin inducție că $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ , pentru orice $n \geq 1$ . Verifică apoi rezultatul pentru $n = 8$ prin calcul direct.

Răspunsuri și explicații

1. a) $2, 5, 8, 11, 14$ ; b) $2, 5, 10, 17, 26$ ; c) $- 1, 2, - 3, 4, - 5$ ; d) $\frac{1}{2}, \frac{1}{6}, \frac{1}{12}, \frac{1}{20}, \frac{1}{30}$ . La c), factorul $(- 1)^{n}$ dă alternanța semnelor, începând cu minus.

2. $3 n - 1 = 59 \Rightarrow n = 20$ , deci este termenul de rang $20$ . Pentru $100$ : $3 n - 1 = 100 \Rightarrow n = \frac{101}{3}$ , care nu este număr natural, deci $100$ nu apare în șir.

3. $2, 7, 12, 17, 22$ . Diferența a doi termeni consecutivi este constant $5$ , deci este o progresie aritmetică cu rația $r = 5$ ; formula explicită este $a_{n} = 5 n - 3$ .

4. $3, 6, 12, 24, 48$ . Este o progresie geometrică cu $q = 2$ , deci $a_{n} = 3 \cdot 2^{n - 1}$ .

5. $1, 5, 13, 29, 61$ . Diferențele: $4, 8, 16, 32$ — nu sunt constante, deci nu e progresie aritmetică. Rapoartele: $5; 2, 6; 2, 23 \dots; 2, 10 \dots$ — nu sunt constante, deci nu e nici geometrică.

6. Fals. Regula spune doar cum se trece de la un termen la următorul; fără punctul de plecare, ea este satisfăcută de o infinitate de șiruri. De exemplu $a_{n + 1} = 2 a_{n}$ descrie și $1, 2, 4, \dots$ , și $5, 10, 20, \dots$ , și $- 3, - 6, - 12, \dots$ . Sunt necesare atâtea valori de pornire câți termeni anteriori folosește recurența.

7. Fals. Pentru o progresie geometrică raportul trebuie să fie constant, nu doar să se apropie de o valoare. La Fibonacci, rapoartele sunt $1; 2; 1, 5; 1, 667; 1, 6; 1, 625; \dots$ — diferite între ele, deci șirul nu este progresie geometrică.

8. Termenii: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55$ . Rapoartele: $1, 000$ ; $2, 000$ ; $1, 500$ ; $1, 667$ ; $1, 600$ ; $1, 625$ — oscilează, apropiindu-se de $φ \approx 1, 618$ , secțiunea de aur.

9. Termenii: $1, 2, 4, 7, 11, 16$ . Verificare: $n = 1$ dă $1 + 0 = 1$ ✓. Pas: dacă $a_{k} = 1 + \frac{k ( k - 1 )}{2}$ , atunci

$a_{k + 1} = a_{k} + k = 1 + \frac{k ( k - 1 )}{2} + k = 1 + \frac{k ^{2} - k + 2 k}{2} = 1 + \frac{k ( k + 1 )}{2},$

adică formula pentru rangul $k + 1$ . ✓

10. Termenii: $1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}$ . Conjectura: $a_{n} = \frac{1}{n}$ . Verificare: $a_{1} = 1 = \frac{1}{1}$ ✓. Pas: dacă $a_{k} = \frac{1}{k}$ , atunci $a_{k + 1} = \frac{1/ k}{1 + 1/ k} = \frac{1/ k}{( k + 1 ) / k} = \frac{1}{k + 1}$ ✓. Prin inducție, $a_{n} = \frac{1}{n}$ pentru orice $n \geq 1$ .

11. Recurența: $C_{n + 1} = 1, 05 \cdot C_{n}$ , cu $C_{0} = 2000$ . Este chiar definiția unei progresii geometrice de rație $1, 05$ , deci formula explicită este $C_{n} = 2000 \cdot 1, 0 5^{n}$ . De exemplu $C_{3} = 2315, 25$ lei.

12. $b_{n + 1} = a_{n + 1} - 1 = 3 a_{n} - 3 = 3 (a_{n} - 1) = 3 b_{n}$ , deci $(b_{n})$ e progresie geometrică de rație $3$ , cu $b_{1} = 1$ . Rezultă $b_{n} = 3^{n - 1}$ și $a_{n} = 3^{n - 1} + 1$ . Verificare: $a_{5} = 81 + 1 = 82$ , iar din recurență $a_{5} = 3 \cdot 28 - 2 = 82$ ✓.

13. Definiția „al $n$ -lea număr prim" determină fără ambiguitate fiecare termen, deci este o definiție corectă. Nu se cunoaște însă o formulă simplă care să dea direct termenul de rang $n$ ; practic, pentru al $50$ -lea termen ai avea de aplicat un algoritm (de exemplu ciurul lui Eratostene) și de numărat primele $50$ de numere prime, obținând $229$ .

14. a) $a_{1} = 7$ , $a_{n + 1} = a_{n} - 4$ ; explicit $a_{n} = 7 - 4 (n - 1) = 11 - 4 n$ . b) $b_{1} = 5$ , $b_{n + 1} = \frac{1}{2} b_{n}$ ; explicit $b_{n} = 5 \cdot (\frac{1}{2})^{n - 1} = \frac{5}{2 ^{n - 1}}$ .

15. a) $a_{2} = 5$ , $a_{3} = 13$ , $a_{4} = 29$ . b) Inducție: verificarea $n = 1$ dă $2^{2} - 3 = 1 = a_{1}$ ✓; pasul: din $a_{k} = 2^{k + 1} - 3$ rezultă $a_{k + 1} = 2 (2^{k + 1} - 3) + 3 = 2^{k + 2} - 3$ ✓. Conform principiului inducției, formula e adevărată pentru orice $n \geq 1$ . (Este Exemplul 6.)

16. $a_{1} = \frac{1}{2}$ , $a_{5} = \frac{9}{6} = \frac{3}{2}$ , $a_{10} = \frac{19}{11}$ . Inegalitatea $\frac{2 n - 1}{n + 1} < 2$ revine, prin înmulțire cu $n + 1 > 0$ , la $2 n - 1 < 2 n + 2$ , adică $- 1 < 2$ , adevărat pentru orice $n \geq 1$ .

17. Termenii: $1, 4, 9, 16, 25$ — pătratele perfecte, deci conjectura este $a_{n} = n^{2}$ . Verificare: $a_{1} = 1 = 1^{2}$ ✓. Pas: dacă $a_{k} = k^{2}$ , atunci $a_{k + 1} = k^{2} + 2 k + 1 = (k + 1)^{2}$ ✓. Prin inducție, $a_{n} = n^{2}$ pentru orice $n \geq 1$ .

18. Verificare: $n = 1$ : $F_{1} = 1$ și $F_{3} - 1 = 2 - 1 = 1$ ✓. Pas: presupunem $F_{1} + \dots + F_{k} = F_{k + 2} - 1$ ; adunând $F_{k + 1}$ obținem $F_{k + 2} + F_{k + 1} - 1 = F_{k + 3} - 1$ , folosind chiar recurența lui Fibonacci ✓. Prin inducție, relația e adevărată pentru orice $n \geq 1$ . Verificare pentru $n = 8$ : $1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = 54$ , iar $F_{10} - 1 = 55 - 1 = 54$ ✓.

De reținut

Un șir de numere reale este o funcție $f : N^{*} \to R$ , notată $(a_{n})_{n \geq 1}$ ; contează ordinea, iar termenii se pot repeta.
Un șir se poate defini în trei feluri: descriptiv, prin formula termenului general ( $a_{n}$ exprimat în funcție de $n$ ) și prin relație de recurență (regulă de trecere plus termeni de pornire).
O definiție prin recurență este completă numai împreună cu termenii de pornire: atâția câți termeni anteriori folosește regula (unul la $a_{n + 1} = f (a_{n})$ , doi la Fibonacci).
Progresiile sunt șiruri recurente: $a_{n + 1} = a_{n} + r$ pentru cea aritmetică, $b_{n + 1} = b_{n} q$ pentru cea geometrică; formula termenului general este tocmai forma lor explicită.
Trecerea de la recurență la formula explicită urmează tiparul calculezi termeni → conjecturezi → demonstrezi prin inducție; conjectura singură, oricâți termeni ar acoperi, nu este demonstrație.

Greșeli frecvente

Recurență fără termen de pornire. „Șirul definit de $a_{n + 1} = 3 a_{n}$ " nu este un șir, ci o familie infinită de șiruri. Scrie întotdeauna și valoarea inițială.
Confuzia dintre rang și termen. $a_{5}$ este termenul de rang $5$ ; întrebarea „ce rang are termenul $59$ ?" cere rezolvarea unei ecuații în $n$ , iar soluția trebuie să fie număr natural.
Enumerarea luată drept definiție. Din „ $2, 4, 8, \dots$ " nu rezultă unic continuarea; fără regulă, orice continuare e legitimă. La astfel de cerințe, precizează regula presupusă.
Conjectura declarată demonstrație. Găsirea formulei explicite prin observarea primilor termeni este doar primul pas; la mate-info, formula trebuie confirmată prin inducție, folosind chiar relația de recurență în pasul inductiv.
Indexare schimbată pe parcurs. Dacă pornești de la $a_{1}$ , formula progresiei geometrice este $b_{n} = b_{1} q^{n - 1}$ ; dacă pornești de la $a_{0}$ , devine $b_{n} = b_{0} q^{n}$ . Fixează convenția la început și verifică formula pe primul termen.

Aplică acasă

Recurența din bucătărie. Alege o rețetă care se dublează („pentru fiecare porție în plus, adaugi…") și scrie relația de recurență dintre cantitatea pentru $n$ porții și cea pentru $n + 1$ porții. Găsește apoi formula explicită și calculează, fără să parcurgi pașii, cantitatea pentru $12$ porții.
Fibonacci în natură. Numără spiralele de pe un con de brad, de pe o floarea-soarelui sau petalele câtorva flori. Compară numerele obținute cu termenii șirului lui Fibonacci și notează care apar. Calculează apoi, pe caiet, rapoartele $F_{n + 1} : F_{n}$ pentru primii zece termeni și observă cum se apropie de $1, 618$ .
Un șir propriu. Inventează o relație de recurență de forma $a_{n + 1} = k a_{n} + t$ , cu numere alese de tine, și un prim termen. Calculează primii șase termeni, caută substituția $b_{n} = a_{n} + c$ care transformă șirul într-o progresie geometrică și verifică formula explicită găsită pe termenul al șaselea.

Pentru părinți și profesori

Lecția deschide unitatea de șiruri a programei de matematică-informatică și aduce elementul care lipsește din trunchiul comun: definirea prin recurență. Este momentul în care noțiunea de șir se leagă riguros de cea de funcție și, în același timp, punctul în care matematica se întâlnește cel mai direct cu informatica — o relație de recurență este, cuvânt cu cuvânt, o funcție recursivă cu caz de bază.

Ce verifică lecția: calculul corect al termenilor dintr-o recurență (cu atenție la substituția în expresie, nu doar la ultimul rezultat), distincția dintre rang și termen, aflarea rangului prin rezolvarea unei ecuații cu soluție naturală, scrierea progresiilor sub formă recurentă și, cel mai important, disciplina de a demonstra prin inducție orice formulă conjecturată. Întrebări bune de control: „De ce nu e suficientă regula, fără primul termen?"; „De ce are Fibonacci nevoie de doi termeni de pornire?"; „Ai verificat formula pe cinci termeni — de ce nu e destul?".

Semne că elevul a înțeles: trece fără ezitare de la forma recurentă la cea explicită și înapoi, folosește recurența ca instrument în pasul inductiv (nu ca decor) și nu confundă „raportul se apropie de o valoare" cu „raportul este constant". La Bacalaureat (M1), tipul de cerință este exact cel din Exemplul 6: se dau primii termeni de calculat, apoi se cere demonstrarea formulei explicite prin inducție — o structură în care redactarea corectă a celor două etape aduce cea mai mare parte a punctajului.

Întrebări frecvente

Ce este un șir de numere reale, definit riguros? Este o funcție definită pe mulțimea numerelor naturale nenule cu valori reale, $f : N^{*} \to R$ . Valoarea $f (n)$ se notează $a_{n}$ și se numește termenul de rang $n$ , iar șirul se notează $(a_{n})_{n \geq 1}$ . Spre deosebire de o mulțime, un șir ține cont de ordine și poate repeta valori.

Care sunt modurile de definire a unui șir? Trei: descriptiv (se spune în cuvinte ce reprezintă termenii, de exemplu „al $n$ -lea număr prim"), prin formula termenului general (o expresie în $n$ , de exemplu $a_{n} = 3 n - 1$ ) și prin relație de recurență (regula de trecere de la un termen la următorul, plus termenii de pornire).

Ce înseamnă că un șir este definit prin recurență? Înseamnă că fiecare termen se calculează din cei dinaintea lui, printr-o regulă fixă, pornind de la una sau mai multe valori date. De exemplu, $a_{1} = 1$ și $a_{n + 1} = 2 a_{n} + 3$ generează $1, 5, 13, 29, \dots$ Fără termenul de pornire, regula nu determină șirul.

De ce are nevoie șirul lui Fibonacci de doi termeni de pornire? Pentru că regula lui, $F_{n + 2} = F_{n + 1} + F_{n}$ , folosește doi termeni anteriori: ca să calculezi al treilea termen îți trebuie primii doi. În general, o recurență care se sprijină pe $k$ termeni anteriori are nevoie de $k$ valori inițiale.

Cum trec de la o relație de recurență la formula termenului general? Calculezi primii termeni, cauți un tipar (uneori după o substituție de tipul $b_{n} = a_{n} + c$ , care transformă șirul într-o progresie), formulezi conjectura și o demonstrezi prin inducție matematică, folosind relația de recurență în pasul inductiv.

Este orice progresie un șir definit prin recurență? Da. Progresia aritmetică este șirul dat de $a_{n + 1} = a_{n} + r$ , iar cea geometrică de $b_{n + 1} = b_{n} \cdot q$ , împreună cu primul termen. Formulele $a_{n} = a_{1} + (n - 1) r$ și $b_{n} = b_{1} q^{n - 1}$ sunt versiunile lor explicite.

Poate un șir să fie definit corect fără o formulă? Da. Șirul numerelor prime, $2, 3, 5, 7, 11, \dots$ , este perfect determinat de descrierea sa, deși nu se cunoaște o formulă simplă pentru termenul de rang $n$ . Definiția e corectă atât timp cât fiecare termen este determinat fără ambiguitate.

Ce legătură are recurența cu programarea? Este aceeași structură: o funcție recursivă are un caz de bază (termenul de pornire) și un apel care reduce problema (regula de recurență). De aceea șirurile recurente se implementează direct, fie recursiv, fie iterativ printr-o buclă care actualizează o variabilă.