# Prove $\big\lfloor{\frac{n}{2}}\big\rfloor+\Big\lfloor\frac{\lceil\frac{n}{2}\rceil}{2}\Big\rfloor+\cdots = n - 1$.

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.

• Have you tried proving this with induction? – 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} &=\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}

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