Witam,
\(f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1\ .\)
Jak zabrać się do rozwiązania tej rekurencji ?
Chciałbym funkcjami tworzącymi, ale nie bardzo mi to wychodzi.
Tzn zaczynam tak:
\(F(x) = \sum_{n=0}^{\infty}f_nx^n\)
Wtedy:
\(F(x) = f_0 + f_1x + \sum_{n=2}^{\infty} \frac{2n-1}{n}f_{n-1}x^n - \sum_{n=2}^{\infty}\frac{n-1}{n} f_{n-2}x^n + \sum_{n=2}^{\infty}1x^n\)
Jak to rozwiązać ? Sami widzicie, że jest kłopot z tymi ułamkowymi współczynnikami.
Rozwiązanie rekurencji
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
octahedron
- Expert
- Posty: 6762
- Rejestracja: 19 mar 2011, 00:22
- Otrzymane podziękowania: 3034 razy
- Płeć:
\(f_n=\frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2}+1\\
f_n=\left(2-\frac{1}{n}\right)f_{n-1}-\left(1-\frac{1}{n}\right)f_{n-2}+1\\
\sum\limits_{n=2}^\infty f_n x^{n-2}=\sum\limits_{n=2}^\infty\left(2-\frac{1}{n}\right)f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty\left(1-\frac{1}{n}\right)f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty x^{n-2}\\
\sum\limits_{n=2}^\infty f_n x^{n-2}=2\sum\limits_{n=2}^\infty f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-2}x^{n-2}+\frac{1}{1-x}\\
\sum\limits_{n=2}^\infty f_n x^n=2x\sum\limits_{n=2}^\infty f_{n-1}x^{n-1}-\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-1}x^n-x^2\sum\limits_{n=2}^\infty f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-2}x^n+\frac{x^2}{1-x}\\
F(x)-x=2xF(x)-\int\sum\limits_{n=2}^\infty f_{n-1}x^{n-1}\,dx-x^2F(x)+\int\sum\limits_{n=2}^\infty f_{n-2}x^{n-1}\,dx+\frac{x^2}{1-x}\\
F(x)-x=2xF(x)-\int F(x)\,dx-x^2F(x)+\int xF(x)\,dx+\frac{x^2}{1-x}\\
F'(x)-1=2F(x)+2xF'(x)-F(x)-2xF(x)-x^2F'(x)+xF(x)+\frac{2x-x^2}{(1-x)^2}\\
(x-1)^2F'(x)+(x-1)F(x)=\frac{1}{(1-x)^2},\quad F(0)=0\\
F(x)=\frac{1}{2(x-1)}-\frac{1}{2(x-1)^3}=-\frac{1}{2(1-x)}+\left(\frac{1}{4(1-x)}\right)''=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\left(\sum\limits_{n=0}^\infty x^n\right)''=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\sum\limits_{n=2}^\infty n(n-1)x^{n-2}=\\
=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\sum\limits_{n=0}^\infty (n+2)(n+1)x^n=\sum\limits_{n=0}^\infty\left(\frac{(n+2)(n+1)}{4}-\frac{1}{2}\right)x^n\\
f_n=\frac{(n+2)(n+1)}{4}-\frac{1}{2}=\frac{1}{4}n(n+3)\\\)
f_n=\left(2-\frac{1}{n}\right)f_{n-1}-\left(1-\frac{1}{n}\right)f_{n-2}+1\\
\sum\limits_{n=2}^\infty f_n x^{n-2}=\sum\limits_{n=2}^\infty\left(2-\frac{1}{n}\right)f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty\left(1-\frac{1}{n}\right)f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty x^{n-2}\\
\sum\limits_{n=2}^\infty f_n x^{n-2}=2\sum\limits_{n=2}^\infty f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-1}x^{n-2}-\sum\limits_{n=2}^\infty f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-2}x^{n-2}+\frac{1}{1-x}\\
\sum\limits_{n=2}^\infty f_n x^n=2x\sum\limits_{n=2}^\infty f_{n-1}x^{n-1}-\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-1}x^n-x^2\sum\limits_{n=2}^\infty f_{n-2}x^{n-2}+\sum\limits_{n=2}^\infty\frac{1}{n}f_{n-2}x^n+\frac{x^2}{1-x}\\
F(x)-x=2xF(x)-\int\sum\limits_{n=2}^\infty f_{n-1}x^{n-1}\,dx-x^2F(x)+\int\sum\limits_{n=2}^\infty f_{n-2}x^{n-1}\,dx+\frac{x^2}{1-x}\\
F(x)-x=2xF(x)-\int F(x)\,dx-x^2F(x)+\int xF(x)\,dx+\frac{x^2}{1-x}\\
F'(x)-1=2F(x)+2xF'(x)-F(x)-2xF(x)-x^2F'(x)+xF(x)+\frac{2x-x^2}{(1-x)^2}\\
(x-1)^2F'(x)+(x-1)F(x)=\frac{1}{(1-x)^2},\quad F(0)=0\\
F(x)=\frac{1}{2(x-1)}-\frac{1}{2(x-1)^3}=-\frac{1}{2(1-x)}+\left(\frac{1}{4(1-x)}\right)''=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\left(\sum\limits_{n=0}^\infty x^n\right)''=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\sum\limits_{n=2}^\infty n(n-1)x^{n-2}=\\
=-\frac{1}{2}\sum\limits_{n=0}^\infty x^n+\frac{1}{4}\sum\limits_{n=0}^\infty (n+2)(n+1)x^n=\sum\limits_{n=0}^\infty\left(\frac{(n+2)(n+1)}{4}-\frac{1}{2}\right)x^n\\
f_n=\frac{(n+2)(n+1)}{4}-\frac{1}{2}=\frac{1}{4}n(n+3)\\\)