984501234

11

2. LICZBY NATURALNE. INDUKCJA MATEMATYCZNA

gdzie k $5 n + 1. Dalsza część dowodu oparta jest na standardowym triku kombina-torycznym: policzymy ilość elementów zbioru C* na dwa sposoby, a następnie porównamy. Przy każdym ustalonym A € [X]^fc istnieje dokładnie k elementów a takich, że (a, A) € Cfc. Zatem otrzymujemy

\C_k\=k-\[X]^k\.

Z drugiej strony, jeśli ustalimy element a € X oraz para (a, A) € Ck, to pozostałe elementy zbioru A, czyli elementy zbioru A \ {a} są wybrane ze zbioru n-elementowego Y = X \ {a}. Korzystając z założenia indukcyjnego otrzymujemy równość

Porównując obydwie równości dostajemy ostatecznie

n + 1

^:    k

|[A?|

n +1    n!    /n+1\

k ' (k- l)!-(n-(*-!))! ⁼ \ k J’ co kończy dowód.

Przy pomocy współczynników Newtona można także zapisać wzór dwumienny Newtona pozwalający na obliczanie wyrażeń postaci (x + y)ⁿ, gdzie n jest dowolną liczbą naturalną.

Zanim zapiszemy ten wzór przyjmijmy pewną umowę, tzw. konwencję sumacyjną przyjętą powszechnie nie tylko w matematyce. Wielką literą grecką E (czytaj „sigma”) będziemy oznaczać dodawanie liczb, których wartości zależą od elementów należących do danego zbioru. Zatem jeśli A = {1,2,...,n}, to symbol

Tl ak oznacza sumę a\ + «2 + • • • + a_n.

k€A

Na przykład, jeśli A = {1,2,3,4,5}, to

k² = 1 + 2² + 3² + 4² + 5² = 55,

keA

a jeśli A = {2,4,6,7}, to

y k² = 2² + 4² + 6² + 7² = 105.

keA

Na ogół jednak tym danym zbiorem będzie u nas odcinek zbioru liczb naturalnych postaci {1,2,..., n} lub {m, m + 1, to + 2,..., n}. Wtedy piszemy

&k — ^ai + &2 ■+■ • • • + o,_n lub a,k — a_m ■+■ ^am+1 + • • • + &_n-

fc=l    k=m

Czasami wygodnie jest założyć, że zbiór A zaczyna się od 0, wtedy

^ak — y ak — ao + ai H----+ a_n-

keA    k=o