2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you try to calculate $x(n)$ for small values of $n$? $\endgroup$ – 5xum Dec 10 '14 at 13:12
  • $\begingroup$ 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 $\endgroup$ – iymz Dec 10 '14 at 13:14
  • $\begingroup$ Is $n$ a real variable? $\endgroup$ – Alex Silva Dec 10 '14 at 15:00
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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