Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$?


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

share|cite|improve this question
I think this or a very similar question has already been posed here, but I can't find it. – joriki Nov 10 '12 at 5:01
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...) – coffeemath Nov 10 '12 at 6:37
@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](‌​ng-function-and-explicit-formula). That produces link text. – Brian M. Scott Nov 10 '12 at 6:48
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. – Henry T. Horton Dec 7 '12 at 19:53

LAST UPDATE - promised :-) (Explicit Formula)

Let's start by subtracting both equations :

$$f(2n+1)-f(2n)=f(n)-f(n-1)$$ we have too $\ f(2(n+1))=f(n+1)+f(n)+2$ so that :


Setting $\ g(n):=f(n+1)-f(n)\ $ will return the simpler : $$g(2n)=g(n-1),\quad g(2n+1)=g(n)$$

and the even simpler for $n>0$ ( with $g(0)=1,\ g(1)=2$ ) : $$\boxed{g(n)=g(2n+1)=g(2n+2)}$$ The initial values of $1$ and $2$ will 'propagate' all the way long alternating a power of $2$ number of ones with the same number of twos getting (starting with $n=0$) : $$1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1$$

A simpler rule to retain this is to consider $n+1$ : if the two most significant bits of $(n+1)$ are $10_2$ then $g(n)=2$ else (for $11_2$) we get $g(n)=1$ or more formally : $$ g(n)=\begin{cases} &1\quad \text{if}\quad n=0\quad \text{or}\quad 2^m+2^{m-1}\le n+1<2^{m+1}\ \text{with}\ m\in\mathbb{N}\ \ \\ &2\quad \text{if}\quad 2^m\le n+1<2^m+2^{m-1}\ \text{with}\ m\in\mathbb{N}\\ \end{cases} $$ Let's try to get a generating function for the $g(n)$ terms : \begin{align} G(x)&=\sum_{n=0}^\infty g(n)\,x^n\\ &=1+2x^1+x^2+2(x^3+x^4)+x^5+x^6+2(x^7+x^8+x^9+x^{10})+x^{11}+\cdots\\ &=\frac 1{1-x} +x^1+(x^3+x^4)+(x^7+x^8+x^9+x^{10})+(x^{15}+\cdots+x^{22})+\cdots\\ &=\frac {1+x(1-x)+x^3(1-x^2)+x^7(1-x^4)+x^{15}(1-x^8)+\cdots}{1-x}\\ &=\frac {1+\sum_{k=0}^\infty x^{2\cdot 2^k}(1-x^{2^k})/x}{1-x}\\ &=\frac {1+\left(S(x^2)-S(x^3)\right)/x}{1-x}\\ \end{align}

Using the $S$ series (convergent for $|x|<1$) defined by : $\ \displaystyle S(x):=\sum_{n=0}^\infty x^{2^n}$

(the continued fraction of $S\left(\frac12\right)$ was studied by Shallit here and given at OEIS)
Let's observe that (of course!) $G\left(\frac 1{10}\right)=1.212211222211112222222211\cdots$

Concerning $f(n)$ it will be obtained using $\ f(n+1)=f(n)+g(n)\ $ with $f(0)=0$ getting : $$0, 1, 3, 4, 6, 8, 9, 10, 12, 14, 16, 18, 19, 20, 21, 22, 24, 26, 28, 30, 32$$

You may obtain this result using following generating function (remembering that the effect of the division by $1-x$ is to obtain the partial sums) : \begin{align} F(x)&=\frac{1x+2x^2+1x^3+2x^4+2x^5+1x^6+1x^7+2x^8+2x^9+2x^{10}+2x^{11}+1 x^{12}+\cdots}{1-x}\\ &=0+1x + 3x^2 + 4x^3 + 6x^4 + 8x^5 + 9x^6 + 10x^7 + 12x^8 +14x^9+16x^{10}+\cdots\\ \end{align}

or formally : $$F(x)=\frac{x\,G(x)}{1-x}=\frac {x+S(x^2)-S(x^3)}{(1-x)^2}$$

An explicit formula for $f(n)$ should be (for $n>1$ and $m:=\lfloor\log_2(n)\rfloor$) : $$ f(n)=\begin{cases} &2\;n-2^{m-1}\quad &\text{if}\quad 2^m\le n<2^m+2^{m-1}\ \text{with}\ m\in\mathbb{N}\\ &\ n+2^m-1\quad &\text{if}\quad 2^m+2^{m-1}\le n<2^{m+1}\ \text{with}\ m\in\mathbb{N}\ \ \\ \end{cases} $$

Challenge (updated)

I don't have a proof of this but I'll conjecture that for $x\in \mathbb{N}^*$ (with $m:=\lfloor\log_2(x)\rfloor$) :

$$ \lim_{k \to \infty} \frac{f(2^kx)}{2^k}=\begin{cases} &2\;x-2^{m-1}\quad &\text{if}\quad 2^m\le x<2^m+2^{m-1}\ \text{with}\ m\in\mathbb{N}\\ &\ x+2^m\quad &\text{if}\quad 2^m+2^{m-1}\le x<2^{m+1}\ \text{with}\ m\in\mathbb{N}\ \ \\ \end{cases} $$

Interesting problem. Hoping this helped a little,

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.