Aplicarea metodei inductiei matematice

3) Etapa de inducție: dovedesc că afirmația este adevărată pentru n = k + 1, adică, ..

1 + 3 + 5 +. + (2k - 1) + (2k + 1) = (k + 1) 2. Conform ipotezei, suma primilor termeni k din partea stângă este egală cu k 2. Deci, ceea ce este necesar pentru a dovedi, poate fi scris ca:

k 2 + (2k + 1) = (k + 1) 2.

dar este evident.

Exemplul 15. Să se arate că, pentru orice număr natural n 3 n + 5n divizibil cu 6.

Dovada. Inducția de bază include: atunci când n = 1, numărul n 3 + 5n = 6 împărțit la 6. Să presupunem că pentru anumite numere k 3 k + 5k divizibil cu 6. Folosind aceasta, încearcă să demonstreze că, dacă și (k + 1) + 3 5 (k + 1) este divizibil cu 6. conversie Draw:

(K + 1) 3 + 5 (k + 1) = k 3 + 3k 2 + 3k + 1 + 5k + 5 = = (k 3 + 5k) + (3k 2 + 3k) + 6 = (k 3 + 5k ) + 3k (k + 1) + 6.

Primul termen din această sumă se împarte la 6, prin ipoteză, al doilea termen este, de asemenea, divizibil cu 6, din cauza numerelor k, k + 1 un mod necesar chiar. Prin urmare, întreaga sumă este divizibil cu 6, după cum este necesar.

Ca un alt exemplu, vom demonstra o teorema cu privire la numărul de subseturi de un set finit.

Teorema 4. Setul format din n elemente, n 2 este subseturi diferite.

Dovada. Noi folosim inducție pe numărul n. Dacă setul A = constă dintr-un singur element, apoi un subset - este 0. Lor 2, însă teorema atunci când n = 1 este adevărat (bază de inducție). Presupunem că orice set de elemente k are 2k subseturi. Luați în considerare setul

Toate subseturi împărțiți în 2 tipuri. Primul tip subseturi otnesom care nu conțin ak + 1. În ipoteza unor astfel de subseturi de 2k. Celălalt subset conține ak + 1, iar numărul lor este egal cu 2k, deoarece fiecare dintre ele este obținut prin adăugarea ak + 1 la unul dintre subseturi de primul tip. Toate subseturi ale setului A conține:

2k + 2 = 2k x 2k = 2k + 1,

QED.