# Explicit Formula Given a Recursion

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$

-
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](http://math.stackexchange.com/questions/213882/recursive-sequence-generati‌​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 :

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

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,

-