Solve recursive equation $f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$

Solve recursive equation:

$$f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$ $f_0 = 0, f_1 = 1$

What I have done so far:

$$f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$

I multiplied it by $n$ and I have obtained:

$$nf_n = (2n-1)f_{n-1}-(n-1)f_{n-2} + n- n[n=0]$$ $$\sum nf_n x^n = \sum(2n-1)f_{n-1}x^n-\sum (n-1)f_{n-2}x^n + \sum n x^n$$

$$\sum nf_n x^n = \sum(2n-1)f_{n-1}x^n-\sum (n-1)f_{n-2}x^n + \frac{1}{(1-z)^2} - \frac{1}{1-z}$$

But I do not know what to do with parts with $n$. I suppose that there can be useful derivation or integration, but I am not sure. Any HINTS?

-

If $g(x)$ is your generating function, then $g'(x)=\sum nf_nx^{n-1}$, so $xg'(x)=\sum nf_nx^n$. Then

$$\sum(2n-1)f_{n-1}x^n=x\sum(2n+1)f_nx^n=2x^2g'(x)+xg(x)\;,$$

and you can handle the remaining summation similarly. I’ve not checked to see whether the resulting differential equation is nice or nasty. Note that your variable name changed from $x$ to $z$ in the last two terms.

-
I am not sure, but it should not be$\sum(2n-1)f_{n-1}x^n=x\sum(2n+1)f_{n-1}x^{n-1}$? Or maybe it does not matter? –  JosephConrad Apr 4 '13 at 19:03
@JosephConrad: I shifted the index one place. Think of it as substituting $m=n-1$: then $\sum(2n-1)f_{n-1}x^n=\sum(2m+1)f_mx^{m+1}$. Now pull out an $x$, and rename $m$ back to $n$. –  Brian M. Scott Apr 4 '13 at 19:05
Ok, I agree. Thanks a lot for help! I will try to finish this task with such substitution. –  JosephConrad Apr 4 '13 at 19:08
@JosephConrad: You’re welcome! –  Brian M. Scott Apr 4 '13 at 19:09

Let's take a shot at this: $$f_n - f_{n - 1} = \frac{n - 1}{n} (f_{n - 1} - f_{n - 2}) + 1$$ This immediately suggests the substitution $g_n = f_n - f_{n - 1}$, so $g_1 = f_1 - f_0 = 1$: $$g_n - \frac{n - 1}{n} g_{n - 1} = 1$$ First order linear non-homogeneous recurrence, the summing factor $n$ is simple to see here: $$n g_n - (n - 1) g_{n - 1} = n$$ Summing: \begin{align*} \sum_{2 \le k \le n} (k g_k - (k - 1) g_{k - 1}) &= \sum_{2 \le k \le n} k \\ n g_n - 1 \cdot g_1 &= \frac{n (n + 1)}{2} - 1 \\ g_n &= \frac{n + 1}{2} \\ f_n - f_{n - 1} &= \frac{n + 1}{2} \\ \sum_{1 \le k \le n} (f_n - f_{n - 1}) &= \sum_{1 \le k \le n} \frac{k + 1}{2} \\ f_n - f_0 &= \frac{1}{2} \left( \frac{n (n + 1)}{2} + n \right) \\ f_n &= \frac{n (n + 3)}{4} \end{align*} Maxima tells me this checks out. Pretty!

-
Pretty impressive solution. Could you explain me 2 things: 1) what non-homogeneous recurrence stands for? 2) Why are we summing that equation ($n g_n - (n - 1) g_{n - 1} = n$)? –  JosephConrad Apr 4 '13 at 19:57
@JosephConrad, (1) that is just the name for such an equation; (2) sum up to get the $n g_n$ (most of the rest of the sum telescopes away, the summing factor is designed to make this happen), same to get the $f_n$ in the end. Look closely, there shouldn't be any real mystery in this. –  vonbrand Apr 4 '13 at 20:02
Yes, now I understand what is going on :) Thanks for explanation! –  JosephConrad Apr 4 '13 at 20:14

Did you try difference equations? The original expression can be rewritten as (denote $\Delta f_k=f_{k}-f_{k-1}$) $$\Delta f_{k}=\frac{k-1}{k}\Delta f_{k-1}+1 =\frac{k-1}{k} \cdot \frac{k-2}{k-1} \Delta f_{k-2} + \frac{k-1}{k}+1= \ldots =\frac{1}{k} \Delta f_1 + \frac{k-1}{k} \\ + \frac{k-2}{k-1}+\ldots + 1 = \frac{1}{k} \Delta f_1 + k - H_k$$ By summing both sides over $k$ and using boundary values you should get something like (I haven't checked the algebra!) $$f_n= H_n + \frac{n(n+1)}{2}-(n+1)(H_n-1)$$

-