Witam. Mam problem z utworzeniem funkcją tworząca do ciągu:
\(\displaystyle{ h _{n}= {n \choose 2} , n \ge 0}\)
Bardzo proszę o pomoc, bo nie wiem jak to ugryźć.
funkca tworząca
-
darlove
- Użytkownik
- Posty: 218
- Rejestracja: 20 gru 2007, o 12:36
- Płeć: Mężczyzna
- Lokalizacja: Londyn
- Pomógł: 39 razy
funkca tworząca
Trzeba isc w odwrotna strone niz przy rozwiazywaniu rekurencji przez funkcje tworzace. Najpierw znajdz rekurencje na \(\displaystyle{ {n \choose 2}}\). To bedzie
\(\displaystyle{ {n \choose 2}={{n-1}\choose 2}+{{n-1}\choose 1}\quad}\) (dziala dla wszystkich \(\displaystyle{ n}\)).
Teraz pomnoz stronami przez \(\displaystyle{ x^n}\):
\(\displaystyle{ {n \choose 2}x^n=x{{n-1}\choose 2}x^{n-1}+(n-1)x^n.}\)
A teraz wysumuj zaczynajac od \(\displaystyle{ n=2}\). Zauwaz, ze \(\displaystyle{ {n \choose k}= 0}\), gdy \(\displaystyle{ n<k}\).
\(\displaystyle{ \sum_{n=2}^{\infty} {n \choose 2}x^n =x \sum_{n=2}^{\infty} {{n-1}\choose 2}x^{n-1}+ \sum_{n=2}^{\infty}(n-1)x^n=\\
x \sum_{n=1}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=2}^{\infty}(n-1)x^{n-2}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=1}^{\infty}nx^{n-1}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=0}^{\infty}nx^{n-1}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\left(\sum_{n=0}^{\infty}x^n\right)'=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\left(\frac{1}{1-x}\right)'=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\frac{1}{(1-x)^2}.}\)
Teraz, jesli oznaczymy nasza funkcje przez \(\displaystyle{ A_x}\), to dostajemy rownanie
\(\displaystyle{ A_x=xA_x+\frac{x^2}{(1-x)^2}}\),
z czego juz latwo obliczyc \(\displaystyle{ A_x}\).
\(\displaystyle{ {n \choose 2}={{n-1}\choose 2}+{{n-1}\choose 1}\quad}\) (dziala dla wszystkich \(\displaystyle{ n}\)).
Teraz pomnoz stronami przez \(\displaystyle{ x^n}\):
\(\displaystyle{ {n \choose 2}x^n=x{{n-1}\choose 2}x^{n-1}+(n-1)x^n.}\)
A teraz wysumuj zaczynajac od \(\displaystyle{ n=2}\). Zauwaz, ze \(\displaystyle{ {n \choose k}= 0}\), gdy \(\displaystyle{ n<k}\).
\(\displaystyle{ \sum_{n=2}^{\infty} {n \choose 2}x^n =x \sum_{n=2}^{\infty} {{n-1}\choose 2}x^{n-1}+ \sum_{n=2}^{\infty}(n-1)x^n=\\
x \sum_{n=1}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=2}^{\infty}(n-1)x^{n-2}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=1}^{\infty}nx^{n-1}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\sum_{n=0}^{\infty}nx^{n-1}=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\left(\sum_{n=0}^{\infty}x^n\right)'=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\left(\frac{1}{1-x}\right)'=\\
x \sum_{n=2}^{\infty} {{n}\choose 2}x^{n}+ x^2\frac{1}{(1-x)^2}.}\)
Teraz, jesli oznaczymy nasza funkcje przez \(\displaystyle{ A_x}\), to dostajemy rownanie
\(\displaystyle{ A_x=xA_x+\frac{x^2}{(1-x)^2}}\),
z czego juz latwo obliczyc \(\displaystyle{ A_x}\).