Widzieliśmy już, że dla \( n\in \mathbb{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.