1

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!

Krzysztof Lewko
  • 2,312
  • You are almost there, your reorganized recurrence is $n (f_n - f_{n - 1}) = (n - 1) (f_{n - 1} - f_{n - 2}) + n$, this screams for $g_n = n (f_n - f_{n - 1})$... – vonbrand Apr 05 '14 at 23:14

2 Answers2

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 $$

Claude Leibovici
  • 260,315
  • Hey wow, yes its correct answer (according to wolframalpha), but i still dont know magic did you use here, would love to see some elaboration on this! – Krzysztof Lewko Apr 05 '14 at 11:42
  • @Chris. I am not good at all in this area. As said, it has been an emprical approach based on a lot of multilinear regression. I just wanted to help with my small tricks. What amazed me if that I started with $f_0=0$ and $f_1=1$ and I had the quadratic part of the solution ! Cheers. – Claude Leibovici Apr 05 '14 at 11:49
2

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).$$

Marko Riedel
  • 61,317