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

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.

• Write $$f(n):=\left\lceil\dfrac{n}{2}\right\rceil$$ for each positive integer $n$. Let $f_k$ be the $k$-time iteration of $f$ for $k=0,1,2,\ldots$ (i.e., $f_0$ is the identity function, and $f_k:=f_{k-1}\circ f$ for all $k=1,2,\ldots$), and define $$g_k(n):=\left\lfloor\dfrac{f_{k-1}(n)}{2}\right\rfloor$$ for all $k=1,2,3,\ldots$. Prove that $g_k(n)$ is the number of all integers $m$ such that $2\leq m\leq n$ and $$m\equiv 2^{k-1}+1\pmod{2^k}\,.\tag{*}$$ Show also that, for every integer $m$ such that $2\leq m\leq n$, there exists a unique positive integer $k$ such that (*) is true – Batominovski Sep 5 at 9:29
• Coincidence that $\frac{\displaystyle\int_{0}^{n}\lfloor x\rfloor\, dx}{\displaystyle\int_{0}^{n} \{x\}\, dx}=n-1$ ? – C Squared Sep 6 at 5:45

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} holds by induction on $$k$$.

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} &=\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