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.
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.