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&gt;1$.

$f(2n+1) = f(n) + f(n-1) + 1$ for $n&gt;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]
Define
$$
\begin{align*}
A(x) &amp;= \frac{1}{x^2} + 1 + x + x^3, \\
B(x) &amp;= \frac{x^3}{1-x^2} + \frac{x^2}{(1-x^2)^2} - \frac{1}{x^2} - 1 - 2x^2 \\ &amp;=
-\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.