Meditatii matematica - demonstratie formula combinari folosind inductia matematica



Vom demonstra aceasta formula folosind inductia matematica. Aceasta spune ca atunci cand avem de aratat o identitate valabila pentru un anumit numar de termeni (n), daca presupunem ca acea relatie este adevarata pt k termeni si aratam ca ramane adevarata si pt k+1 termeni, oricare ar fi numarul natural k, atunci demonstratia s-a incheiat. Iata cum arata inductia aici:

Presupunem (1) adevarata pentru k termeni. Asta inseamna :


Demonstram atunci ca (1) ramane adevarata si pentru k+1 termeni, adica trebuie aratat ca



In demonstratie vom folosi ce-am presupus adevarat, pentru a ne ajuta in a scurta foarte mult demonstratia. In primul rand, o sa scriu penultimul termen din (3), pentru ca ulterior sa pot folosi cei k termeni in functie de (1). Vom avea:



Observam de asemenea ca fiecare combinare din (2) are la baza k, si nu k+1. Deci pentru a putea folosi eficient (2) cu (4), trebuie ca fiecare membru din (4) sa aiba la baza k, adica sa fie doar termeni de genul combinari de k luate cate...Pentru asta, vom folosi o formula de recurenta:



Pentru demonstratie vom aplica definitia combinarilor in ambele parti ale egalitatii:

Pentru usurinta, vom simplifica relatia membru cu membru. Pentru asta, avem nevoie de formula
(k+1)! = k! * (k+1), care se deduce foarte usor aplicand definitia:
(k+1)! = 1*2*3*...*k*(k+1). Tot produsul pana la k inclusiv fiind k! => q.e.d.
La fel deducem si ca (n-k)! = (n-k-1)!(n-k), lucru ce se observa foarte usor notand n-k = t, adica t! = (t-1)! * t Prin urmare:



Aducand mai departe in membrul drept, la acelasi numitor, k!(n-k-1)!(n-k)(k+1), obtinem:



Si fortand apoi factor comun, avem:



Facand deci toate simplificarile obtinem 1=1 adevarat => Q.e.d.

Revenind la exercitiu, spuneam ca putem aplica aceasta formula de recurenta, pentru a putea folosi rezultatul presupus adevarat pentru cei k termeni. Iata cum:



Orientandu-ne la relatia (2), selectam din fiecare paranteza membrul stang si obtinem



exact ce avem nevoie sa folosim, presupus adevarat, si pe care vom inlocui ulterior cu k*2^(k-1). Apoi rescriem restul termenilor. Putem face asta, intrucat adunarea este asociativa. Obtinem:

.

Vom desface apoi fiecare termen din ultima suma in atatea bucati, cat indica coeficientul. Adica daca avem 3*C_k ^ 2 obtin C_k ^2 + C_k ^2 + C_k ^2. La fel procedam pentru toti acesti termeni din ultima suma. Avem:



Observam ca adunand toti termenii, mai putin ultimul, din fiecare paranteza, obtinem:



adica aproape, ce-am presupus adevarat. Si spun aproape pentru ca lipseste ultimul termen din (2), k*C_k ^k. Aceasta ultima suma obtinuta este, conform cu (2),



Penultimul termen, k*C_k ^(k-1) s-a despartit in k-1 termeni, fiecare a cate C_k ^(k-1), adunate cu al k-lea termen, C_k ^(k-1). Suma devine:



ce-a mai ramas din acele paranteze, adica ultimul termen din fiecare, respectiv:



ultimul termen din (4), k+1. Ultimei sume, daca ii adaugam termenul de la inceput, C_k ^0, putem observa ca este celebra suma 2^k-1. Deci obtinem:



Ultima idee este exact ce trebuie aratat pentru k+1 termeni. Q.e.d.
Protected by Copyscape DMCA Copyright Protection