3
$\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$
2
  • $\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$ Sep 5, 2020 at 9:29
  • 1
    $\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, 2020 at 5:45

2 Answers 2

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

$\endgroup$
2
$\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} $$

$\endgroup$
2
  • $\begingroup$ what is $a_i$?? $\endgroup$ Mar 11, 2020 at 3:19
  • $\begingroup$ $a_{i}$ is either $0$ or $1$. Basically $i$-th digit of $n$ in base $2$ $\endgroup$ Mar 11, 2020 at 3:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .