Witam. Mam do zrobienia takie oto zadanie z funkcją tworzącą. Jego treść: podać funkcję tworzącą dla poniższego równania:
\(\displaystyle{ a _{0} = 1, a _{1} = 1, a _{n} = 2a _{n-1} + 2a _{n-2}}\) \(\displaystyle{ , n > 1}\)
Zrobiłem to w ten sposób, ale nie wiem czy to jest dobrze zrobione:
\(\displaystyle{ A(x) = \sum_{n=0}^{ \infty }a _{n}x ^{n} = \sum_{n=0}^{ \infty }(2a ^{n-1} + a ^{n-2})x ^{n} = \sum_{n=0}^{ \infty }2a ^{n-1} x ^{n} + \sum_{n=0}^{ \infty }a ^{n-2} x ^{n} = \frac{1}{2}\sum_{n=0}^{ \infty }2ax ^{n} + \sum_{n=0}^{ \infty }ax ^{n} = \frac{1}{2} \cdot \frac{1}{1-2ax} + \frac{1}{1 - ax}}\)
Funkcja tworząca
-
drago77
- Użytkownik
- Posty: 52
- Rejestracja: 13 sty 2011, o 16:28
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 11 razy
Funkcja tworząca
Ale trudno się domyśleć bo napisałem coś zbyt zagmatwanie czy że nie wiadomo co chciałem obliczyć?
Funkcja tworząca
Uważasz, że \(\displaystyle{ \sum_{n=0}^{ \infty }2a ^{n-1} x ^{n} = \frac{1}{2}\sum_{n=0}^{ \infty }2ax ^{n}}\)? Z tego wynikałoby, że dla każdego n:
\(\displaystyle{ 2a^{n-1} = \frac{1}{2} \cdot 2a \Leftrightarrow 2a^{n-1} = a \Leftrightarrow 2a^{n-2} = 1 \Leftrightarrow a^{n-2} = \frac{1}{2}}\), a tak jednak nie jest Chyba nie do końca rozumiesz, co powinieneś zrobić, więc może trochę wyjaśnię. A należy wyciągnąć stałą (tutaj \(\displaystyle{ 2}\) przed nawias), a wraz z nią tyle \(\displaystyle{ x}\), zeby potęgi przy \(\displaystyle{ a}\) i \(\displaystyle{ x}\) były takie same:
\(\displaystyle{ \sum_{n=0}^{ \infty }2a^{n-1} x^{n} = 2x\sum_{n=0}^{ \infty }a^{n-1} x^{n-1} = 2x\sum_{n=0}^{ \infty }(ax)^{n-1}}\)
Teraz już chyba widzisz, ze suma jest prawie taka jak \(\displaystyle{ A(x)}\) - brakuje tylko n zamiast n-1 w wykładniku potęgi - ale można podstawić n+1 za n, zakres sumowania zmieni się, ale dla \(\displaystyle{ n=-1}\) i tak przyjmuje się, że wyraz jest zerowy, więc:
\(\displaystyle{ 2x\sum_{n=0}^{ \infty }(ax)^{n-1} = 2x\sum_{n+1=0}^{ \infty }(ax)^{n+1-1} = 2x\sum_{n=-1}^{ \infty }(ax)^{n} = 2x\sum_{n=0}^{ \infty }(ax)^{n} = 2xA(x)}\)
Podobnie robisz z drugą sumą, dostajesz równanie \(\displaystyle{ A(x) = 2x\cdot A(x) + (to, co Ci tu wyjdzie) \cdot A(x)}\), które już rozwiązujesz jak równanie gdzie niewiadomą jest \(\displaystyle{ A(x)}\). Jak to zrobisz to będziesz miał A(x) = , gdzie to po prawej będzie już funkcją tworzącą w postaci zwartej, którą można przerobić na postać jawną (czyli postać taką, gdzie widać jakie jest \(\displaystyle{ a_{n}}\) dla każdego n).
\(\displaystyle{ 2a^{n-1} = \frac{1}{2} \cdot 2a \Leftrightarrow 2a^{n-1} = a \Leftrightarrow 2a^{n-2} = 1 \Leftrightarrow a^{n-2} = \frac{1}{2}}\), a tak jednak nie jest Chyba nie do końca rozumiesz, co powinieneś zrobić, więc może trochę wyjaśnię. A należy wyciągnąć stałą (tutaj \(\displaystyle{ 2}\) przed nawias), a wraz z nią tyle \(\displaystyle{ x}\), zeby potęgi przy \(\displaystyle{ a}\) i \(\displaystyle{ x}\) były takie same:
\(\displaystyle{ \sum_{n=0}^{ \infty }2a^{n-1} x^{n} = 2x\sum_{n=0}^{ \infty }a^{n-1} x^{n-1} = 2x\sum_{n=0}^{ \infty }(ax)^{n-1}}\)
Teraz już chyba widzisz, ze suma jest prawie taka jak \(\displaystyle{ A(x)}\) - brakuje tylko n zamiast n-1 w wykładniku potęgi - ale można podstawić n+1 za n, zakres sumowania zmieni się, ale dla \(\displaystyle{ n=-1}\) i tak przyjmuje się, że wyraz jest zerowy, więc:
\(\displaystyle{ 2x\sum_{n=0}^{ \infty }(ax)^{n-1} = 2x\sum_{n+1=0}^{ \infty }(ax)^{n+1-1} = 2x\sum_{n=-1}^{ \infty }(ax)^{n} = 2x\sum_{n=0}^{ \infty }(ax)^{n} = 2xA(x)}\)
Podobnie robisz z drugą sumą, dostajesz równanie \(\displaystyle{ A(x) = 2x\cdot A(x) + (to, co Ci tu wyjdzie) \cdot A(x)}\), które już rozwiązujesz jak równanie gdzie niewiadomą jest \(\displaystyle{ A(x)}\). Jak to zrobisz to będziesz miał A(x) = , gdzie to po prawej będzie już funkcją tworzącą w postaci zwartej, którą można przerobić na postać jawną (czyli postać taką, gdzie widać jakie jest \(\displaystyle{ a_{n}}\) dla każdego n).