Poniższe Twierdzenie o Dwumianie wyjaśnia pochodzenie tajemniczej nazwy "współczynniki dwumianowe". Twierdzenie to często przypisuje się Pascalowi. Tymczasem było ono już znane indyjskiemu matematykowi Pingala w III wieku p.n.e..
Obserwacja 5.7 [Twierdzenie o Dwumianie]
Dla \( x,y\in \mathbb{R} \) i \( n\in \mathbb{N} \)
\( \displaystyle (x+y)^n=\sum_{i=0}^n{n\choose i}x^iy^{n-i}. \)
Dowód
Przedstawmy najpierw potęgę \( (x+y)^n \) w rozwiniętej formie iloczynu:
\( \underbrace{(x+y)\cdot\ldots\cdot(x+y)}_{n\ razy}. \)
Korzystając z rozdzielności mnożenia, wyrażenie to staje się sumą składników. Każdy taki składnik to iloczyn pewnej liczby \( x \)-ów i pewnej liczby \( y \)-ów, przy czym łącznie iloczyn taki ma \( n \) czynników. A zatem każdy składnik ma postać \( x^k y^{n-k} \). Powstaje on poprzez wybór \( k \) (spośród \( n \)) czynników w iloczynie \( (x+y)\cdot\ldots\cdot(x+y) \), z których do składnika postaci \( x^k y^{n-k} \) wchodzi \( x \) (a tym samym \( (n-k) \) składników, z których wchodzi \( y \)). Tym samym składników postaci \( x^k y^{n-k} \) jest tyle, ile \( k \)-elementowych podzbiorów zbioru \( n \)-elementowego, czyli \( x^k y^{n-k} \) pojawi się w sumie \( {n\choose k} \)-krotnie.
Twierdzenie o Dwumianie można też udowodnić za pomocą indukcji, co pozostawiamy jako ćwiczenie.
Przykład
\( \begin{align*}(a+b)^2 & =a^2+2ab+b^2, \\ (a+b)^3 & =a^3+3a^2b+3ab^2+b^3, \\ (a+b)^4 & =a^4+4a^3b+6a^2b^2+4ab^3+b^4. \end{align*} \)
Dla dowolnego \( n\geq0 \)
Dowód
Wszystkie punkty wynikają trywialnie z Twierdzenia o Dwumianie. (Pierwszy jest oczywisty. Dla dwu pozostałych zauważmy jedynie, że \( (1+1)^n=2^n \), \( (1-1)^n=0 \).) Jednak drugi i trzeci punkt mają ładną interpretację kombinatoryczną.
Istotnie, liczba podzbiorów zbiorów \( n \) elementowego to \( 2^n \). Z drugiej strony licząc te podzbiory, możemy kolejno zliczać podzbiory \( 0,1,2,\ldots \)-elementowe - jest ich \( {n\choose 0},{n\choose 1},{n\choose 2},\ldots \).
Nieco dłuższy jest argument kombinatoryczny dla naprzemiennej sumy \( {n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0 \). Dla \( n=0 \) jest to oczywiste. Natomiast dla \( n>0 \) jest to równoważne stwierdzeniu, że dla \( n \)-elementowego zbioru \( X \)
Załóżmy najpierw, że \( n \) jest nieparzyste. Wtedy każdy podzbiór zbioru \( X \) o parzystej liczbie elementów ma dopełnienie o nieparzystej liczbie elementów, a każdy podzbiór zbioru \( X \) o nieparzystej liczbie elementów ma dopełnienie o parzystej liczbie elementów. Ta bijektywna odpowiedniość dowodzi, że w istocie jest ich tyle samo.
Załóżmy zatem, że \( n \) jest parzyste i ustalmy \( x\in X \). Zdefiniujmy funkcję \( f:\mathcal{P}(X) \mathcal{P}(X) \), kładąc
\( f(Y)= \begin{cases} (X - Y)-\{x\} \mbox{, jeśli } {x}\not\in {Y}\subseteq {X}, \\ (X - Y)\cup\{x\} \mbox{, jeśli } {x}\in {Y}\subseteq {X}. \end{cases} \)
Zauważmy, że \( f \) jest permutacją \( \mathcal{P}(X) \). Rzeczywiście, dla różnych podzbiorów \( Y_1,Y_2\subseteq X \) mamy:
\( f(Y_1)=(X-Y_1)-\{x\}=X-Y_1\neq X-Y_2=(X-Y_2)-\{x\}=f(Y_2), \)
\( f(Y_1)=(X-Y_1)\cup\{x\}\neq(X-Y_1)\cup\{x\}=f(Y_2), \)
To dowodzi, że \( f \) jest injekcją. Dla dowodu surjektywności weźmy dowolne \( Z\subseteq X \). Jeśli \( x\in Z \) to \( f((X-Z)\cup\{x\})=Z \), jeśli zaś \( x\notin Z \) to \( f((X-Z)-\{x\})=Z \). Zatem \( f \) jest permutacją zbioru \( \mathcal{P}(X) \). Co więcej łatwo zauważyć, że dla \( Y \) o parzystej (nieparzystej) liczbie elementów \( f(Y) \) ma nieparzystą (parzystą) liczbę elementów. To dowodzi, że dla parzystego \( n \) podzbiorów \( X \) o parzystej liczbie elementów jest tyle samo co podzbiorów \( X \) o nieparzystej liczbie elementów.