[Solved]: Closed-form solution to recurrence equation

Problem Detail: 

I have a recurrence relation of the form:

$f(0) = f(1) = 1, f(2) = 2$ (initial conditions).

$f(2n) = f(n+1) + f(n) + n$ for $n>1$.

$f(2n+1) = f(n) + f(n-1) + 1$ for $n>1$.

I have been able to simplify this equation a little bit, but I can't seem to find a closed-form solution (and neither can Mathematica with RSolve).

The first few values of $f(n)$ for $n = 0$ to $10$ are:

[1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22]

Asked By : Ryan

Answered By : Yuval Filmus

Define $$ \begin{align*} A(x) &= \frac{1}{x^2} + 1 + x + x^3, \\ B(x) &= \frac{x^3}{1-x^2} + \frac{x^2}{(1-x^2)^2} - \frac{1}{x^2} - 1 - 2x^2 \\ &= -\frac{1}{x^2} -1 - x^2 + \sum_{m=0}^\infty x^{3+2m} + \sum_{m=0}^\infty (2+m) x^{4+2m}. \end{align*} $$ Then the generating series $F(x) = \sum_{n=0}^\infty f(n) x^n$ satisfies the identity $$ F(x) = A(x) F(x^2) + B(x), $$ and so in some sense is given by the "formula" $$ F(x) = B(x) + A(x) B(x^2) + A(x) A(x^2) B(x^4) + A(x) A(x^2) A(x^4) B(x^8) + \cdots. $$ Unfortunately, this formula holds only in the sense of analytic continuation.

If we use Dirichlet series instead of ordinary generating series, we can probably compute the asymptotics of the sequence, along the lines described here. We leave that as an exercise to the reader.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35634

3.2K people like this

 Download Related Notes/Documents