How to solve recursion? I have tried to solve some recursion:
$$f_n  =  \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n} f_{n-2} + 1, \quad f_0 = 0, f_1 = 1$$
I would like to use a generating function:
$$F(x) = \sum_{n=0}^{\infty}f_nx^n$$
Then:
$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$
But As You see I have a problem. Could you help me ?
 A: You have:
$$ x\, F'(x) = \sum_{n=1}^{+\infty} n\,f_n\, x^n,$$
$$ x\, F(x) = \sum_{n=1}^{+\infty} f_{n-1} x^n,$$
$$ x^2\, F'(x) +  x F(x) = \sum_{n=1}^{+\infty}n\, f_{n-1}\, x^n,$$
$$ x^2 F(x) = \sum_{n=2}^{+\infty} f_{n-2} x^n,$$
$$ 2x^2 F(x) + x^3 F'(x) = \sum_{n=2}^{+\infty} n f_{n-2} x^n.$$
The recursion now gives:
$$ xF'(x)-x = 2(x^2 F'(x)+xF(x))-xF(x)-(2x^2 F(x)+x^3 F'(x))+x^2F(x)+\sum_{n=2}^{+\infty}n x^n$$
or just:
$$ (1-x)^2 F'(x) = (1-x)F(x)+\sum_{n=1}^{+\infty}(n+1)x^n$$
$$ F'(x) = \frac{F(x)}{(1-x)}-\frac{1}{(1-x)^2}+\frac{1}{(1-x)^4}.$$
By setting $F(x)=G(x)-\frac{1}{2(1-x)}+\frac{1}{2(1-x)^3}$ we get the ODE:
$$ G'(x) = \frac{G(x)}{1-x},$$
so:
$$ F(x) = \frac{K}{1-x}+\frac{1}{2(1-x)^3}.$$
Since $F(x)$ has an only pole of order three in $x=1$, we have that $f_n$ is a second degree-polynomial in $n$. By interpolating the first three values we further get:
$$ f_n = \frac{n(n+3)}{4}.$$
A: I may have something that helps you.
You can equivalently write your equations in the form $S^2 f_{n} = \frac{2n + 3}{n+2} S f_n - \frac{n+1}{n+2} f_n + 1$, where $S f_n = f_{n+1}$. Now we have $\left[(n+2)S^2 - (2n+3) S + (n+1) \right] f_n = \left[(n+2)S - (n+1) \right](S-1) f_n = 1$. Define $g_n = (S-1)f_n = f_{n+1} - f_n$. The equation reduces to $(n+2) g_{n+1} - (n+1) g_n = 1$. Solve for $g_n$ and after that solve $g_n = (S-1)f_n$ for $f_n$.
