2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Batominovski Sep 5 at 9:29
  • $\begingroup$ Coincidence that $\frac{\displaystyle\int_{0}^{n}\lfloor x\rfloor\, dx}{\displaystyle\int_{0}^{n} \{x\}\, dx}=n-1$ ? $\endgroup$ – C Squared Sep 6 at 5:45
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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.