# Recurrence equation - floor problem

I'm having trouble solving this recurrence equation:

$$x(n) = x\left(\left\lfloor \frac n2\right\rfloor \right) + n,\quad x(1)=1$$

I`m trying to find non-recurrence equation:

$$x(n) = 2n - 1$$

But this is not correct, because it does not solve for the equation above.

• Did you try to calculate $x(n)$ for small values of $n$? – 5xum Dec 10 '14 at 13:12
• x(1) = 1 x(2) = 3 x(3) = 4 x(4) = 7 x(5) = 8 x(6) = 10 x(7) = 11 x(8) = 15 x(9) = 16 x(10) = 18 x(11) = 19 x(12) = 22 x(13) = 23 x(14) = 25 x(15) = 26 x(16) = 31 x(17) = 32 x(18) = 34 x(19) = 35 x(20) = 38 – iymz Dec 10 '14 at 13:14
• Is $n$ a real variable? – Alex Silva Dec 10 '14 at 15:00

## 1 Answer

Let $S(n)$ the sum of the digits in the binary expansion of the integer $n$. After some computations, we guess the formula $x(n)=2n-S(n)$. This is true for $n=1,2,...$. We show the formula by induction. Let $n\geq 2$, and suppose that the formula is true for $k\leq n$. Put $n+1=b_0+2b_1+\cdots 2^s b_s$, with $b_j=0$ or $1$. Then $\displaystyle m=[\frac{n+1}{2}]=b_1+2b_2+\cdots+2^{s-1}b_s$. By induction, $x(m)=2m-S(m)=n+1-b_0-(b_1+b_2+\cdots+b_s)=n+1-S(n+1)$. Hence $x(n+1)=2(n+1)-S(n+1)$ and we are done.