1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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})$... $\endgroup$ – vonbrand Apr 5 '14 at 23:14
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Krzysztof Lewko Apr 5 '14 at 11:42
  • $\begingroup$ @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. $\endgroup$ – Claude Leibovici Apr 5 '14 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.