Witam czy mógłby mi ktoś na to zadanie rzucić chociaż troche światła bo nie wiem jak się za nie nawet zabrać ;// Najlepiej z jakimś jaśniejszym wyjaśnieniem z góry dziekuje
Znajdź Funkcje Tworzacą, a następnie znajdz prostsze rekurencje:
\(\displaystyle{ \left\{\begin{array}{l} a _{0}=1 \\ a_{n+1}= \sum_{n}^{k=0} a_{k} F_{n-k}+(-1)^{n+1},n \ge 0, gdzie \ F_{n},\n \ge 0, \oznacza ciag\ Fibonacciego \end{array}}\)
Prosze o szybka pomoc od tego zalezy moje zaliczenie ;p
Funkcja Tworzacą ciag fibonacciego wazne
Funkcja Tworzacą ciag fibonacciego wazne
takie dostałem zadanie na kolokwium sam go nie wymyśliłem więc ..... moze da sie go jakos zacząć ???-- 9 wrz 2010, o 17:15 --Umiał by ktoś chociaż to zacząć bo jest mi to bardzo potrzebne od tego zalezy moje zycie ;p
-
abc666
Funkcja Tworzacą ciag fibonacciego wazne
Tak można wyprowadzić wzór na prostszą rekurencję.
\(\displaystyle{ a_{n+2}+a_{n+1}= \sum^{n+1}_{k=0} a_{k} F_{(n+1)-k}+(-1)^{n}+\sum^{n}_{k=0} a_{k} F_{n-k}+(-1)^{n+1}=\\ \sum^{n+1}_{k=0} a_{k} F_{(n+1)-k}+\sum^{n}_{k=0} a_{k} F_{n-k}=\\
a_{n+1}F_{0}+\sum^{n}_{k=0} a_{k} F_{(n+1)-k}+\sum^{n}_{k=0} a_{k} F_{n-k}=\\
0+\sum^{n}_{k=0}a_{k}(F_{(n+1)-k}+F_{n-k})=\sum^{n}_{k=0}a_{k}F_{(n+2)-k}=\\ \sum^{n+2}_{k=0}a_{k}F_{(n+2)-k}-a_{n+1}F_1-a_{n+2}F_{0}=
a_{n+3}-a_{n+1}\\\text{czyli}\\
a_{n+2}+a_{n+1}=a_{n+3}+(-1)^n-a_{n+1}\\
a_{n+3}=a_{n+2}+2a_{n+1}+(-1)^{n+1}}\)
Jednak pewnie nie o to chodziło panu Krajce
EDIT
Ok, trochę pomądrkowałem i takie coś wyszło
Niech \(\displaystyle{ Z(x)}\) oznacza funkcję tworzącą naszego ciąg, wtedy mamy
\(\displaystyle{ Z(x)=\sum_{n=0}^{\infty} a_nx^n=\sum_{n=1}^{\infty} a_nx^n+[x^0]\cdot 1=\\
\sum_{n=0}^{\infty} a_{n+1}x^{n+1}+1=\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k}+(-1)^{n+1} \right) x^{n+1}+1=\\ x\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k} \right) x^{n}-1+\sum_{n=1}^{\infty} (-1)^{n+1}x^{n+1}+1=\\
x\underbrace{\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k} \right) x^{n}}_{\text{splot}}+\sum_{n=0}^{\infty} (-1)^{n}x^{n}=(*)}\)
Czyli dostajemy
\(\displaystyle{ (*)=xF(x)Z(x)+\frac{1}{1-x}}\)
gdzie \(\displaystyle{ F(x)}\) to funkcja tworząca ciągu Fibonacciego, która wynosi
\(\displaystyle{ F(x)=\frac{x}{1-x-x^2}}\)
Czyli dostajemy
\(\displaystyle{ Z(x)=\frac{x^2}{1-x-x^2}\cdot Z(x)+\frac{1}{1-x}}\)
Czyli po przekształceniach
\(\displaystyle{ Z(x)=\frac{x^2+x-1}{(1+x)^2(2x-1)}}\)
\(\displaystyle{ a_{n+2}+a_{n+1}= \sum^{n+1}_{k=0} a_{k} F_{(n+1)-k}+(-1)^{n}+\sum^{n}_{k=0} a_{k} F_{n-k}+(-1)^{n+1}=\\ \sum^{n+1}_{k=0} a_{k} F_{(n+1)-k}+\sum^{n}_{k=0} a_{k} F_{n-k}=\\
a_{n+1}F_{0}+\sum^{n}_{k=0} a_{k} F_{(n+1)-k}+\sum^{n}_{k=0} a_{k} F_{n-k}=\\
0+\sum^{n}_{k=0}a_{k}(F_{(n+1)-k}+F_{n-k})=\sum^{n}_{k=0}a_{k}F_{(n+2)-k}=\\ \sum^{n+2}_{k=0}a_{k}F_{(n+2)-k}-a_{n+1}F_1-a_{n+2}F_{0}=
a_{n+3}-a_{n+1}\\\text{czyli}\\
a_{n+2}+a_{n+1}=a_{n+3}+(-1)^n-a_{n+1}\\
a_{n+3}=a_{n+2}+2a_{n+1}+(-1)^{n+1}}\)
Jednak pewnie nie o to chodziło panu Krajce
EDIT
Ok, trochę pomądrkowałem i takie coś wyszło
Niech \(\displaystyle{ Z(x)}\) oznacza funkcję tworzącą naszego ciąg, wtedy mamy
\(\displaystyle{ Z(x)=\sum_{n=0}^{\infty} a_nx^n=\sum_{n=1}^{\infty} a_nx^n+[x^0]\cdot 1=\\
\sum_{n=0}^{\infty} a_{n+1}x^{n+1}+1=\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k}+(-1)^{n+1} \right) x^{n+1}+1=\\ x\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k} \right) x^{n}-1+\sum_{n=1}^{\infty} (-1)^{n+1}x^{n+1}+1=\\
x\underbrace{\sum_{n=0}^{\infty} \left( \sum_{k=0}^{n}a_kF_{n-k} \right) x^{n}}_{\text{splot}}+\sum_{n=0}^{\infty} (-1)^{n}x^{n}=(*)}\)
Czyli dostajemy
\(\displaystyle{ (*)=xF(x)Z(x)+\frac{1}{1-x}}\)
gdzie \(\displaystyle{ F(x)}\) to funkcja tworząca ciągu Fibonacciego, która wynosi
\(\displaystyle{ F(x)=\frac{x}{1-x-x^2}}\)
Czyli dostajemy
\(\displaystyle{ Z(x)=\frac{x^2}{1-x-x^2}\cdot Z(x)+\frac{1}{1-x}}\)
Czyli po przekształceniach
\(\displaystyle{ Z(x)=\frac{x^2+x-1}{(1+x)^2(2x-1)}}\)