Widzieliśmy już, że dla n∈N
\displaystyle (1+x)^m ={m \choose 0}x^0 + {m \choose 1}x + {m \choose 2}x^2+\ldots+{m \choose m-1}x^{m-1}+{m \choose m}x^m =\sum_{n=0}^m {m \choose n}x^n.
Przyjrzyjmy się teraz rozwinięciu w szereg funkcji (1+x)^y , gdzie y\in\mathbb{R} jest parametrem. Rozwinięcie takie okaże się bardzo przydatne w rozwiązywaniu wielu przykładów. Aby poznać ciąg odpowiadający tej funkcji wprowadźmy definicję.
Uogólniony symbol dwumianowy { y \choose n } , gdzie y\in\mathbb{R} oraz n\in\mathbb{N} jest oznaczeniem na
{ y \choose n }\ =\ \frac{y^{\underline{n}}}{n!}\ =\ \frac{y\cdot(y-1)\cdot\ldots\cdot(y-(n-1))}{1\cdot2\cdot\ldots\cdot(n-1)\cdot n}.
Uwaga
Oczywiście dla y\in\mathbb{N} spełniającego dodatkowo y\geq n , uogólniony symbol dwumianowy { y \choose n } jest liczbą n -elementowych podzbiorów zbioru y -elementowego.
Twierdzenie 7.4
Dla liczby rzeczywistej y oraz liczby naturalnej n zachodzi
\displaystyle (1+x)^y=\sum_{n=0}^{\infty}{ y \choose n }x^n.
Wniosek 7.5
Dla liczby naturalnej m zachodzi
\displaystyle \frac{1}{(1-x)^{m+1}}=\sum_{n=0}^{\infty}{ m+n \choose n }x^n.
Dowód
Dowód zostawiony jest jako ćwiczenie
Przykład
Policzmy sumę
\displaystyle \sum_{k=0}^nk^2=1+4+9+\ldots+n^2.
Zacznijmy od znalezienia zwartej postaci funkcji tworzącej {G}(x)=\sum_{n=0}^{\infty}n^2x^n . Korzystając z Wniosku 7.5 otrzymujemy:
\displaystyle \frac{1}{1-x} = \sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n, (8)
\displaystyle \frac{1}{(1-x)^2} = \sum_{n=0}^{\infty}{n+1 \choose n }x^n\ =\ \sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n. (9)
Po przekształceniu równości (9) uzyskuje się
\displaystyle \sum_{n=0}^{\infty}nx^n= \frac{1}{(1-x)^2} -\frac{1}{1-x}. (10)
Powołując się ponownie na Wniosek 7.5 otrzymujemy
\displaystyle \frac{1}{(1-x)^3} =\sum_{n=0}^{\infty}{ n+2 \choose n}x^n =\frac{1}{2}\sum_{n=0}^{\infty}n^2x^n+\frac{3}{2}\sum_{n=0}^{\infty}nx^n+\sum_{n=0}^{\infty}x^n,
co w połączeniu z równościami (9) oraz (10) daje zwartą postać funkcji tworzącej {G}(x) dla ciągu 1,4,9,\ldots,n^2,\ldots :
\displaystyle {G}(x)=\sum_{n=0}^{\infty}n^2x^n =\frac{2}{(1-x)^3}-\frac{3}{(1-x)^2}+\frac{1}{1-x}.
Naszym zadaniem było jednakże policzenie funkcji tworzącej H(x) dla ciągu 1,1+4,1+4+9,\ldots,1+4+9+\ldots+n^2,\ldots , tzn. ciągu sum początkowych wyrazów ciągu 1,4,9,\ldots,n^2,\ldots . Aby uzyskać {H}(x) wystarczy więc skorzystać ze wzoru (7) i podzielić {G}(x) przez 1-x . Tak więc poszukiwanym rozwiązaniem są współczynniki funkcji tworzącej
{H}(x)=\frac{{G}(x)}{1-x} =\frac{2}{(1-x)^4}-\frac{3}{(1-x)^3}+\frac{1}{(1-x)^2}.
Korzystając po raz kolejny z Wniosku 7.5 otrzymujemy
\begin{align*}{H}(x) & =2\sum_{n=0}^{\infty}{n+3 \choose n}x^n-3\sum_{n=0}^{\infty}{n+2 \choose n}x^n+\sum_{n=0}^{\infty}{n+1 \choose n}x^n \\ & =\sum_{n=0}^{\infty}(\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n)x^n. \end{align*}
W konsekwencji zachodzi równość
\displaystyle \sum_{k=1}^nk^2={x^n}{H}(x)=\frac{2n^3+3n+n}{6}.
Przykład
Wracamy do przykładu z monetami. Występowały tam funkcje tworzące postaci
{A_k}(x) = 1+x^k+x^{2k}+x^{3k}+\ldots,
dla k=1,5,10,25 i 50 . Z równości (7) wiemy, że
1+x^k+x^{2k}+x^{3k}+\ldots, =\frac{1}{1-x^k}
tak więc:
\begin{align*}{A}(x)= {A_1}(x) & = \frac{1}{1-x}, \\ {B}(x)= {A}(x)\cdot {A_5}(x) & =\frac{{A}(x)}{1-x^5}, \\ {C}(x)={B}(x)\cdot {A_{10}}(x) & =\frac{{B}(x)}{1-x^{10}}, \\ {D}(x)={C}(x)\cdot {A_{25}}(x) & =\frac{{C}(x)}{1-x^{25}}, \\ {E}(x)= {D}(x)\cdot {A_{50}}(x) & =\frac{{D}(x)}{1-x^{50}}, \end{align*}
skąd natychmiast:
\begin{align*}{A}(x) & =1+x{A}(x), \\ {B}(x) & ={A}(x)+x^5{B}(x), \\ {C}(x) & ={B}(x)+x^{10}{C}(x), \\ {C}(x) & ={D}(x)+x^{25}{C}(x), \\ {D}(x) & ={E}(x)+x^{50}{D}(x). \end{align*}
Równości te dają zależności między współczynnikami:
a_n=1,\quad b_n=a_n+b_{n-5},\quad c_n=b_n+c_{n-10},\quad d_n=c_n+d_{n-25},\quad \quad e_n=d_n+e_{n-50}.
Wykorzystując te zależności rekurencyjne możemy wypełnić następującą tabelę:
\begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 0 & 5 & 10 & 15 & 2 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100 \\ \hline\hline a_n & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline b_n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline c_n & 1 & 2 & 4 & 6 & 9 & 12 & 16 & 10 & 25 & 30 & 36 & 42 & 49 & 56 & 64 & 72 & 81 & & 100 & & 121 \\ \hline d_n & 1 & & & & & 13 & & & & & 49 & & & & & 121 & & & & & 242 \\ \hline e_n & 1 & & & & & & & & & & 50 & & & & & & & & & & 292 \\ \hline \end{array}
Pół dolara można rozmienić na 50 sposobów. Z kolei rozmieniać jednego dolara można na aż 292 sposoby. Do problemu tego wrócimy jeszcze w następnym wykładzie.