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

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} $$

Answer 2

$$ \forall (x,n) \in \mathbb{R}×\mathbb{N}, \: \left \lfloor \frac{\lfloor x \rfloor}{n} \right \rfloor = \left \lfloor \frac{x}{n} \right \rfloor$$

$$\forall n\in \mathbb{N}, \: n=\left \lfloor \frac{n}{2} \right \rfloor + \left \lceil \frac{n}{2} \right \rceil$$

Applying Hermite's identity, we have \begin{equation} n= \left \lfloor \frac{n}{2} \right \rfloor + \left \lfloor \frac{n+1}{2} \right \rfloor \end{equation}

Therefore $$\forall n \in \mathbb{N}, \; \left \lceil \frac{n}{2} \right \rceil = \left \lfloor \frac{n+1}{2} \right \rfloor$$
Define a function $f: \mathbb{N} \to \mathbb{Z}$ \begin{align*} f(n) &= \left \lceil \frac{n}{2} \right \rceil = \left \lfloor \frac{n+1}{2} \right \rfloor \\ f^{[2]}(n)&=f(f(n)); \; \; f^{[k]}(n)=f(f^{[k-1]}(n)) \end{align*}
Then \begin{align*} f(f(n)) &= \left \lfloor \frac{\left \lfloor \frac{n+1}{2} \right \rfloor + 1}{2} \right \rfloor = \left \lfloor \frac{\left \lfloor \frac{n+1+2}{2} \right \rfloor}{2} \right \rfloor \\ &= \left \lfloor \frac{n+2^0+2^1}{2^2} \right \rfloor \end{align*}

it is not difficult to show by induction that:

\begin{align*} f^{[k]}(n) &= \left \lfloor \frac{n+\sum_{j=0}^{k-1} 2^j}{2^k} \right \rfloor = \left \lfloor \frac{n+2^k-1}{2^k} \right \rfloor \\ &=\left \lfloor \frac{n-1}{2^k} \right \rfloor +1 \end{align*}
We see that the above sum is equivalent to \begin{align*} \sum_{k=0}^\infty \left \lfloor \frac{f^{[k]}(n)}{2} \right \rfloor &= \sum_{k=0}^\infty \left \lfloor \frac{f^{[k]}(n)-1}{2} + \frac{1}{2} \right \rfloor \\ &= \sum_{k=0}^\infty \left \lfloor f^{[k]}(n)-1 \right \rfloor - \left \lfloor \frac{f^{[k]}(n)-1}{2} \right \rfloor \\ &= \sum_{k=0}^\infty \left \lfloor \frac{n-1}{2^k} \right \rfloor - \left \lfloor \frac{\left \lfloor \frac{n-1}{2^k} \right \rfloor}{2} \right \rfloor \\ &= \sum_{k=0}^\infty \left \lfloor \frac{n-1}{2^k} \right \rfloor - \left \lfloor \frac{n-1}{2^{k+1}} \right \rfloor \\ &= \left \lfloor \frac{n-1}{2^0} \right \rfloor = n-1 \end{align*}

Answer 3

Alternative to the prior post, only the following lemmas to be considered (also the ones i'd mentioned in the previous post): $$\forall (x,n)\in \mathbb{R}×\mathbb{N}, \; \left \lceil \frac{\lceil x \rceil}{n} \right \rceil = \left \lceil \frac{x}{n} \right \rceil$$ or equivalently, $$\forall (m,n,x)\in \mathbb{Z}×\mathbb{N}×\mathbb{R}, \: \left\lceil \frac{\lceil x \rceil + m}{n} \right\rceil = \left\lceil \frac{x+m}{n} \right\rceil$$ $$\forall (a,b)\in \mathbb{Z}×\mathbb{N}, \; \left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a-1}{b} \right \rfloor +1 \iff \left\lfloor \frac{a}{b} \right \rfloor = \left\lceil \frac{a+1}{b} \right\rceil - 1$$ Last, but not least $$\forall (x,n)\in \mathbb{R}×\mathbb{N}, \; \lceil nx \rceil = \sum_{k=0}^{n-1} \left\lceil x-\frac{k}{n} \right\rceil$$ or in other words,
Hermite's Ceiling Function Identity (which can easily be obtained by substituting $x\to -x$ into the Hermite's Floor Function Identity)

The validity of all of these shall be left as exercises to the readers

Substituting for n=2 and $x\to x/2$ on the last lemma, \begin{align} \lceil x \rceil = \left\lceil \frac{x-1}{2}\right\rceil + \left\lceil \frac{x}{2} \right\rceil \end{align}

Let $f: \mathbb{N} \to \mathbb{Z}$ such that $$f(n) = \left \lceil \frac{n}{2} \right \rceil$$

\begin{align*} f_k(n) &= \underbrace{f(f(...(f(n))...))}_{\text{k times}} \\ \\ &= \left \lceil \frac{\left \lceil \frac{...\left \lceil \tfrac{n}{2} \right \rceil ...}{2} \right \rceil}{2} \right \rceil = \left \lceil \frac{n}{2^k} \right \rceil \end{align*}

The above sum is then equivalent to \begin{align*} \sum_{k=0}^\infty \left \lfloor \frac{f_k(n)}{2} \right \rfloor &= \sum_{k=0}^\infty \left( \left \lceil \frac{f_k(n)+1}{2} \right \rceil-1 \right) \\ &= \sum_{k=0}^\infty \left\lceil \frac{\left\lceil \frac{n}{2^k} \right\rceil -1}{2} \right\rceil = \sum_{k=0}^\infty \left\lceil \frac{\frac{n}{2^k}-1}{2} \right\rceil \\ &= \sum_{k=0}^\infty \left\lceil \frac{n}{2^{k+1}} - \frac{1}{2} \right\rceil \\ &= \lim_{m\to\infty} \, \sum_{k=0}^{m-1} \left\lceil \frac{n}{2^k} \right\rceil - \left\lceil \frac{n}{2^{k+1}} \right \rceil \\ &= \lim_{m\to\infty} n-\left\lceil \frac{n}{2^m} \right \rceil \end{align*} Set $M=\left\lceil \log_2(n+1) \right\rceil \iff 0<2^{M-1}\leq n < 2^M $
Thus $$ \forall m\in [M,\infty) \cap \mathbb{N} ,\; \; 0<\frac{n}{2^m}<1 \implies \left\lceil \frac{n}{2^m} \right\rceil = 1 $$ Therefore, as $m\to \infty, m\in \mathbb{N}$, one obtains $$\sum_{k=0}^\infty \left\lfloor \frac{f_k(n)}{2} \right\rfloor= \lim_{m\to \infty} n - \left\lceil \frac{n}{2^m} \right \rceil = n-1$$

as was to be demonstrated.

∎

Answer 4

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