# Closed-form solution to recurrence equation

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]

• Are you looking for asymptotic bounds? Note that we can approximate the first equality as $f(2n) = 2f(n) + n$, i.e., $f(n) = 2f(n/2) + n/2$, which by the Master theorem solves to $\Theta(n \lg n)$. The second equation is approximately $f(n) = 2f(n/2) + 1$, which by the Master theorem solves to $\Theta(n)$. Therefore, I'd expect your final answer to be $\Omega(n)$ and $O(n \lg n)$. Those might be the best bounds possible. Is that tight enough for you? – D.W. Dec 24 '14 at 5:00
• @D.W. Thanks for the asymptotics, but it would be much better if there were exact closed form solutions (of any form). – Ryan Dec 24 '14 at 14:14
• It is naive to expect there to be any better closed form than the recurrence. Do you have any particular reason to think that such a closed form exists? – Yuval Filmus Dec 26 '14 at 6:09

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.