2
$\begingroup$

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]

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Dec 24 '14 at 5:00
  • $\begingroup$ @D.W. Thanks for the asymptotics, but it would be much better if there were exact closed form solutions (of any form). $\endgroup$ – Ryan Dec 24 '14 at 14:14
  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Dec 26 '14 at 6:09
3
$\begingroup$

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.

$\endgroup$

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.