Prove that $\left\lfloor{\frac{n}{2}}\right\rfloor+\left\lfloor\frac{\left\lceil\frac{n}{2}\right\rceil}{2}\right\rfloor+\cdots=n-1$.

Question

Prove that, for $n\in \Bbb{Z}^+$, $$\left\lfloor{\frac{n}{2}}\right\rfloor+\left\lfloor\frac{\left\lceil\frac{n}{2}\right\rceil}{2}\right\rfloor+\left\lfloor\frac{\left\lceil\frac{\left\lceil\frac{n}{2}\right\rceil}{2}\right\rceil}{2}\right\rfloor+\cdots = n - 1\,,$$ where there are $\lceil{\log_2n}\rceil$ addends on the left-hand side.

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.

Answer 1

One may use $n=\lfloor n/2\rfloor+\lceil n/2\rceil$ recursively. So (compare to the comment by @Batominovski), if $f(n)=\lceil n/2\rceil$ and $g(n)=\lfloor n/2\rfloor$, then $n=g(n)+f(n)=g(n)+g(f(n))+f(f(n))=\ldots$, i.e. $$n=f_m(n)+\sum_{k=0}^{m-1}g(f_k(n))\qquad \big[f_0(n)=n,\quad f_{k+1}(n)=f(f_k(n))\big]$$ (induction on $m$). Now put $m=\lceil\log_2 n\rceil$ and notice (well, prove) that $f_m(n)=1$.

The latter is accomplished by noting that we also have $$f_{k+1}(n)=f_k(f(n))=f_k(\lceil n/2\rceil),$$ so that $2^{k-1}<n\leqslant 2^k\implies f_k(n)=1$ holds by induction on $k$.

Answer 2

Any positive integer $n$ satisfies 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} $$