Help me manipulating with exponential generating function (recurrence relation)

Question

I have recurrence relation $f_0=0, f_1=1$ $$f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n}f_{n-2} + 1$$ $$nf_n = nf_{n-1} + (n-1)f_{n-1} - (n-1)f_{n-2} + n$$

I tried to solve it using ordinary generating functions and it turned out to be close to impossible to solve:

$$ln(F(x))' = \frac{(1-x^3)(1-x)^2+x^2}{(x-x^3-x^4)(1-x)^2}$$ where F(x) was generating function for sequence $\langle f_n \rangle$

So i thought exponential generating functions will do the job here, but i can't see the simple trick to solve it... I'd really really appreciate some help on this, because i'm stuck with this problem for like 3 days and i'd really like to solve it by generating functions. Thanks in advance!

Answer 1

Here are the steps which are quite simple, if we know the answer to look for.

Making use of Claude Leibovici's empirical result we put $$ g_n = n (f_n-f_{n-1})$$ to obtain $$ g_n = g_{n-1} + n$$ with $g_1 = f_1-f_0$ and $g_0 = 0.$

This gives $$g_n = f_1-f_0 + \sum_{k=2}^n k$$ or $$g_n = f_1-f_0-1 + \frac{1}{2} n (n+1).$$

Now $$\frac{g_n}{n} = f_n - f_{n-1}$$ so that $$\sum_{k=1}^n \frac{g_k}{k} = f_n - f_0.$$

But $$\sum_{k=1}^n \frac{g_k}{k} = (f_1-f_0-1) H_n + \frac{1}{2} \sum_{k=1}^n (k+1) \\= (f_1-f_0-1) H_n + \frac{1}{2} \left(-1+ \frac{1}{2}(n+1) (n+2)\right)$$ which is $$(f_1-f_0-1) H_n + \frac{1}{4} n (n+3)$$ so that $$f_n = f_0 + (f_1-f_0-1) H_n + \frac{1}{4} n (n+3).$$

Answer 2

I hope I am not wrong.

I started discarding the $1$ in the rhs; writing the first terms, it seems to me that the general formula is $$f_n=f_0+(f_1-f_0) H_n$$ in which appears the harmonic number. Knowing now that the $H_n$ has to appear, I found (almost emprically) that for the recurrence you posted should be $$f_n=f_0+\frac{1}{4} n (n+3)+(f_1-f_0-1) H_n $$