Un bar vinde bonuri de consumație de $$3$$ lei și de $$8$$ lei. Un angajat demonstrează prin inducție că orice sumă întreagă de cel puțin $$14$$ lei se acoperă exact cu bonuri. Ce este ipoteza inductivă în demonstrația lui?

$$P(k)$$ este adevărată pentru un $$k\ge14$$ oarecare

$$P(n)$$ este adevărată pentru orice $$n\ge14$$

Lecția pe scurt · clasa a IX-a · Inducția: baza, ipoteza, pasul

Cum verific o formulă a unui șir prin inducție?

Verifici în două etape. Baza: formula dă primul termen corect. Pasul: presupui formula la $k$ , o pui în regula de recurență și obții formula la $k + 1$ . Exemplu: $a_{1} = 7$ , $a_{n + 1} = 4 a_{n} - 9$ și formula $a_{n} = 4^{n} + 3$ . Baza: $4^{1} + 3 = 7$ . Pasul: din ipoteza $a_{k} = 4^{k} + 3$ și din regulă, $a_{k + 1}$ iese $4^{k + 1} + 3$ . Proba: $a_{2} = 19 = 4^{2} + 3$ . Concluzia: prin inducție, formula este adevărată pentru orice $n \geq 1$ .

Profilul tău de liceu: nu l-ai ales încăProfilul tău: mate-info (M1)Profilul tău: științe ale naturii (M2)Profilul tău: filiera tehnologică (M3); pagina asta e pentru filiera tehnologică (M3) — matematica de mate-info, clasa a IX-a →; pagina asta e pentru filiera tehnologică (M3) — traseul M2, clasa a IX-a → ·

Inducția dovedește o propoziție pentru toate numerele naturale de la un început $n_{0}$ încolo, fără să le încerci pe toate. Ai nevoie de două lucruri: baza, adică propoziția verificată la început, și pasul, adică implicația «dacă este adevărată la $k$ , este adevărată și mai departe».

Pasul poate avansa cu $1$ , dar și cu un salt $s$ , de pildă când adaugi mereu același bon sau același accesoriu. Atunci baza trebuie să aibă exact $s$ valori consecutive, câte una pentru fiecare șir de valori pe care saltul îl produce. În pas folosești numai ipoteza, adică propoziția la un $k$ oarecare, nu propoziția pe care vrei s-o dovedești.

La o formulă dată printr-o regulă de recurență, verifici baza pe primul termen calculat din regulă, apoi înlocuiești $n$ cu $k + 1$ peste tot și folosești ipoteza într-un singur rând marcat. La un număr de variante sau de sume plătibile, pasul arată cum o soluție veche devine una nouă.

Demonstrația se încheie cu concluzia «prin inducție, propoziția este adevărată pentru orice $n \geq n_{0}$ ». Capcanele sunt baza prea scurtă, baza lipsă, pasul care folosește exact ce trebuie dovedit și constanta uitată la înmulțire. Verifici pe o valoare din afara bazei și pe valoarea de dinainte de $n_{0}$ .

De reținut

baza: primul termen din regulă; pasul: $P (k) \Rightarrow P (k + 1)$
formula trebuie să treacă și baza, și pasul
concluzia: prin inducție, adevărată pentru orice $n \geq n_{0}$

Greșeala tipică

Se crede că ipoteza inductivă este propoziția la toți $n$ . Ipoteza este numai propoziția la un $k$ oarecare; dacă ai presupune-o pentru toți $n$ , ai presupune ceea ce vrei să dovedești, iar demonstrația s-ar învârti în cerc.

Exerciții din această mini-lecție

Un bar vinde bonuri de consumație de $3$ lei și de $8$ lei. Un angajat demonstrează prin inducție că orice sumă întreagă de cel puțin $14$ lei se acoperă exact cu bonuri. Ce este ipoteza inductivă în demonstrația lui?
- a) $P (k)$ este adevărată pentru un $k \geq 14$ oarecare
- b) $P (n)$ este adevărată pentru orice $n \geq 14$
- c) $P (k + 3)$ este adevărată
- d) $P (14)$ este adevărată
Vezi răspunsul

Răspuns corect: a) $P (k)$ este adevărată pentru un $k \geq 14$ oarecare

Ipoteza este propoziția la un $k \geq 14$ oarecare, pe care o folosești în pas. Varianta cu «orice $n \geq 14$ » este concluzia, nu ipoteza; $P (k + 3)$ este ceea ce se dovedește în pas; $P (14)$ este o verificare din bază.
Un depozit livrează sticle în baxuri de $4$ și de $5$ sticle. Pentru a dovedi prin inducție că orice număr $n \geq 12$ de sticle se poate livra exact, pasul este $P (k) \Rightarrow P (k + 4)$ . Elevul verifică în bază numerele $12$ , $13$ și $14$ . Ce valoare lipsește din bază?
- a) $11$
- b) $15$
- c) $16$
- d) $4$
Vezi răspunsul

Răspuns corect: b) $15$

Pasul sare din $4$ în $4$ , deci baza are $4$ valori consecutive: $12$ , $13$ , $14$ și $15$ , unde $15 = 3 \cdot 5$ . Valoarea $16$ vine din $12$ prin pas, deci nu mai trebuie verificată; $11$ este sub începutul $12$ și nici nu se poate livra; $4$ este saltul, nu o valoare din bază.
Într-un decantor, cantitatea de nămol, în m³, urmează regula $V_{n + 1} = 0, 5 V_{n} + 6$ , cu $V_{0} = 40$ . Care formulă este adevărată pentru orice $n \geq 0$ ?
- a) $V_{n} = 40 \cdot 0, 5^{n} + 6 n$
- b) $V_{n} = 6 + 34 \cdot 0, 5^{n}$
- c) $V_{n} = 12 + 28 \cdot 0, 5^{n}$
- d) $V_{n} = 28 + 12 \cdot 0, 5^{n}$
Vezi răspunsul

Răspuns corect: c) $V_{n} = 12 + 28 \cdot 0, 5^{n}$

Toate patru dau $V_{0} = 40$ , deci baza nu le separă; le separă pasul. Din regulă, $V_{1} = 0, 5 \cdot 40 + 6 = 26$ și $V_{2} = 0, 5 \cdot 26 + 6 = 19$ . Formula $V_{n} = 12 + 28 \cdot 0, 5^{n}$ dă $26$ și $19$ și respectă pasul: jumătate din $12 + 28 \cdot 0, 5^{k}$ , plus $6$ , este chiar $12 + 28 \cdot 0, 5^{k + 1}$ . Formula $6 + 34 \cdot 0, 5^{n}$ dă $V_{1} = 23$ ; formula $40 \cdot 0, 5^{n} + 6 n$ dă $V_{1} = 26$ , dar $V_{2} = 22$ ; formula $28 + 12 \cdot 0, 5^{n}$ dă $V_{1} = 34$ .

Întrebări conexe

Ce fac dacă formula merge la bază, dar nu și la pas?

Formula este falsă. Pentru $a_{1} = 7$ și $a_{n + 1} = 4 a_{n} - 9$ , formula $a_{n} = 4 n + 3$ dă $7$ la bază, dar $a_{2}$ din regulă este $19$ , iar formula dă $11$ . O formulă bună trebuie să treacă ambele verificări.

Cum găsesc formula unui șir înainte să o dovedesc?

Calculezi primii termeni din regulă și cauți un tipar. Pentru $a_{n + 1} = 4 a_{n} - 9$ cu $a_{1} = 7$ ies $7$ , $19$ , $67$ , $259$ ; fiecare minus $3$ este o putere a lui $4$ : $4$ , $16$ , $64$ , $256$ . Ghicești $a_{n} = 4^{n} + 3$ , apoi o dovedești prin inducție.

Pot începe formula de la n = 0, nu de la n = 1?

Da, dacă șirul pornește de la $a_{0}$ . Pentru $a_{0} = 4$ și $a_{n + 1} = 4 a_{n} - 9$ formula $a_{n} = 4^{n} + 3$ are baza $4^{0} + 3 = 4$ și dă $a_{1} = 7$ . Începutul bazei este primul termen dat în enunț.

Cum arăt că toți termenii unui șir sunt sub o valoare?

Dovedești inegalitatea prin inducție: la bază termenul este mai mic, iar din $a_{k} < M$ deduci $a_{k + 1} < M$ . Pentru $a_{1} = 2$ și $a_{n + 1} = 0, 5 a_{n} + 3$ ai $a_{n} < 6$ : baza este $2 < 6$ , iar pasul dă $a_{k + 1} < 0, 5 \cdot 6 + 3 = 6$ .

Mai merge pasul dacă termenul nou depinde de doi termeni?

Da, dar baza are două valori: pasul folosește $P (k)$ și $P (k + 1)$ ca să obțină $P (k + 2)$ . Pentru $a_{n + 2} = a_{n + 1} + a_{n}$ cu $a_{1} = 1$ și $a_{2} = 1$ , cei doi termeni de început se verifică separat în bază.

Oamenii mai întreabă și: demonstrația prin inducție a unei formule de recurență · baza și pasul la un șir dat prin recurență · cum dovedesc o formulă pentru un șir · verificarea unei formule cu a_(n+1) din a_n