3
$\begingroup$

Suppose we have a function $f$ such that for positive integers $n \ge1$ and $f(0)=0$ and $f(1)=1$ we have:

i) $f(2n + 1) = 2f(n) + 2$

ii) $f(2n) = f(n) + f(n − 1) + 2$

What is the generating function for $f$, and what is the explicit formula for $f(n)$?

Challenge

Moreover, what would be the value of $\lim_{k \to \infty} \frac{f(2^kx)}{2^kx}$, in terms of $x$

  • 0
    I think this or a very similar question has already been posed here, but I can't find it.2012-11-10
  • 0
    joriki: Indeed it was. I gave one of the answers, the title was "Recursive sequence--generating function and explicit formula" posted on Oct 14 by Danielle Huang. (I don't know how to insert a link here...)2012-11-10
  • 0
    @coffeemath: Put the text that you want to appear as a link in square brackets, and immediately follow that by the URL, including `http://`, in ordinary parentheses: `[link text](http://math.stackexchange.com/questions/213882/recursive-sequence-generating-function-and-explicit-formula)`. That produces [link text](http://math.stackexchange.com/questions/213882/recursive-sequence-generating-function-and-explicit-formula).2012-11-10
  • 0
    Apparently the duplicate of this question was deleted because the question was from an ongoing contest (according to a suggested edit to this question). Since the duplicate no longer exists, I'm voting to reopen this question.2012-12-07

1 Answers 1