I suspect for $n\in \Bbb{Z}^+$, and $\lceil{log_2n}\rceil$ addends, $\big\lfloor{\frac{n}{2}}\big\rfloor+\Big\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\Big\rfloor+\Bigg\lfloor\frac{\Big\lceil\frac{\big\lceil\frac{n}{2}\big\rceil}{2}\Big\rceil}{2}\Bigg\rfloor+\cdots = n - 1$. But I don't know how I could prove this. Any ideas? There is an intimate relationship here with a binary tree where each addend is the number of nodes on that layer, and $n$ is the number of leaves.

  • $\begingroup$ Have you tried proving this with induction? $\endgroup$ – Viktor Glombik Mar 11 at 2:31

Any positive integer $n$ satisfy the following equation:

$$ n=\sum_{i=0}^{\left\lfloor\log_{2}{n}\right\rfloor}{\left(a_{i}2^{i}\right)} $$

Substitute it to Your equation to obtain:

$$ \begin{aligned} <your\ equation>&=\sum_{i=0}^{\left\lfloor\log_{2}{n}\right\rfloor}{\left(a_{i}\left(2^{0}+\sum_{j=0}^{i-1}{2^{j}}\right)\right)}-a_{0}\\ &=\sum_{i=0}^{\left\lfloor\log_{2}{n}\right\rfloor}{\left(a_{i}2^{i}\right)}-a_{0}\\ &=n-1 \end{aligned} $$

| cite | improve this answer | |
  • $\begingroup$ what is $a_i$?? $\endgroup$ – Kevin Shannon Mar 11 at 3:19
  • $\begingroup$ $a_{i}$ is either $0$ or $1$. Basically $i$-th digit of $n$ in base $2$ $\endgroup$ – Rezha Adrian Tanuharja Mar 11 at 3:22

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.