How to prove this identity of ceiling function?

Question

My book writes down this identity of least integer function:

$$\lceil x\rceil +\left\lceil x + \frac{1}{n}\right \rceil + \left\lceil x + \frac{2}{n}\right \rceil + \cdots +\left\lceil x + \frac{n -1}{n}\right \rceil = \lceil nx\rceil + n-1 $$.

It didn't deduce it, however. I googled a bit about ceiling function but couldn't find any deduction. It is more like Hermite's Identity of floor function. Can anyone show me how to deduce this?

Answer 1

Another way of doing it is $$f(x)=\lceil x\rceil+\left\lceil x+\frac1n\right\rceil+\dots +\left\lceil x+1-\frac1n\right\rceil - \left\lceil nx\right\rceil$$

We have $$ \begin{align} f\left(x+\frac{1}{n}\right)=&\left\lceil x+\frac1n\right\rceil+\left\lceil x+\frac2n\right\rceil+\dots +\left\lceil x+1\right\rceil - \left\lceil nx+1\right\rceil \\ =&\left\lceil x+\frac{1}{n}\right\rceil+\left\lceil x+\frac2n\right\rceil+\dots +\left\lceil x\right\rceil - \left\lceil nx\right\rceil \\ =&\lceil x\rceil+\left\lceil x+\frac1n\right\rceil+\dots +\left\lceil x+1-\frac{1}{n}\right\rceil - \left\lceil nx\right\rceil\\ =&f(x) \end{align}$$

So $f$ is $\frac1n$-periodic. And we only need to evaluate it over $\left(0,\frac1n\right]$, in which case

$$f(x) = n-1$$

This is because if $x\in(0,\frac{1}{n}]$, then $x,x+\frac{1}{n},\dots,x+\frac{n-1}{n}$ and $nx\in(0,1]$ and $$\left\lceil x\right\rceil = \left\lceil x+\frac{1}{n}\right\rceil=\dots=\left\lceil x+\frac{n-1}{n}\right\rceil=\left\lceil nx\right\rceil=1$$

Answer 2

Using the general property $\lceil u+m\rceil=\lceil u\rceil+m$ if $m\in\mathbb{Z}$, we can rewrite the proposed identity as

$$\lceil x\rceil+\left\lceil x+{1\over n}-1\right\rceil+\left\lceil x+{2\over n}-1\right\rceil+\cdots+\left \lceil x+{n-1\over n}-1 \right\rceil=\lceil nx\rceil$$

which, on simplifying and reordering, becomes

$$\lceil x\rceil+\left\lceil x-{1\over n}\right\rceil+\left\lceil x-{2\over n}\right \rceil+\cdots+\left\lceil x-{n-1\over n}\right \rceil=\lceil nx\rceil$$

The same general property allows us to assume that $0\lt x\le1$, i.e., $(k-1)/n\lt x\le k/n$ for some $1\le k\le n$. It's now easy to see that the first $k$ terms on the left hand side of the proposed identity are equal to $1$ and the rest are $0$, while $k-1\lt nx\le k$ implies $\lceil nx\rceil=k$, and thus the two sides are indeed equal.

Answer 3

Note: This answer provides a combinatorial approach. First we derive a nice formula which is interesting by itself. Then we show that OP's claim is an easy generalisation of it. All of the referred identities can be found at the Wiki page of floor and ceiling functions.

Let's assume we have $p$ objects and we want to distribute these objects evenly on $n$ heaps. The size of a heap is determined by \begin{align*} p=qn+r\qquad\qquad0\leq r < n\tag{1} \end{align*} If $r$ is zero then each heap has size $q=\left\lfloor \frac{p}{n}\right\rfloor$. If the remainder $r$ is greater than zero we have to distribute the $r$ objects evenly on the $n$ heaps, so that $r$ heaps will have size $q+1=\left\lceil\frac{p}{n}\right\rceil$ while $n-r$ heaps will have size $q=\left\lfloor \frac{p}{n}\right\rfloor$.

We obtain \begin{align*} p=\left\lfloor\frac{p}{n}\right\rfloor(n-r)+\left\lceil\frac{p}{n}\right\rceil r \end{align*}

Now we want to address each single heap. Considering the $k$-th heap with $1\leq k \leq n$ we want an expression which gives $1$ in $r$ cases and $0$ in the remaining $n-r$ cases. This can be obtained with \begin{align*} \left\lceil\frac{r-k+1}{n}\right\rceil=[k\leq r] \end{align*} Here we use the Iverson bracket giving one if $k\leq r$ and zero otherwise. Now we can write $p$ as sum of $n$ heaps by iterating $k$ from $1$ to $n$ with a heap heaving either $q=\left\lfloor \frac{p}{n}\right\rfloor$ elements or $q+1$ elements.

We obtain \begin{align*} p&=\sum_{k=1}^{n}\left(q+\left\lceil\frac{r-k+1}{n}\right\rceil\right)\\ &=\sum_{k=1}^{n}\left(\left\lceil q +\frac{r-k+1}{n}\right\rceil\right)\tag{2}\\ &=\sum_{k=1}^{n}\left(\left\lceil \frac{p-k+1}{n}\right\rceil\right)\tag{3}\\ &=\sum_{k=0}^{n-1}\left(\left\lceil \frac{p-k}{n}\right\rceil\right)\tag{4}\\ \end{align*}

Comment:

• In (2) we use for integers $q$ and real $x$ the identity $\lceil q+x \rceil=\lceil q \rceil+x$

• In (3) we use the relationship $p=qn+r$

• In (4) we shift the index by one

Leaving the combinatorial interpretation we can extend the validity of $p$ in (4) to zero and negative values, since the representation (1) is also valid for $p\in \mathbb{Z}$. We get the nice identity

\begin{align*} p=\left\lceil \frac{p}{n}\right\rceil+\left\lceil \frac{p-1}{n}\right\rceil +\cdots+\left\lceil \frac{p-n+1}{n}\right\rceil\qquad\qquad p\in\mathbb{Z}, n\geq 1 \end{align*}

With this formula at hand it's only a small step to proof OPs claim.

Exchanging in (4) the order of summation by replacing $k$ with $n-1-k$ we get

\begin{align*} p=\sum_{k=0}^{n-1}\left(\left\lceil \frac{p-n+1+k}{n}\right\rceil\right) \end{align*}

Since $p$ can be any integer we can set $p=\left\lceil nx\right\rceil+n-1$ with $x$ being real and get

\begin{align*} \left\lceil nx\right\rceil+n-1&=\sum_{k=0}^{n-1}\left\lceil \frac{\left\lceil nx\right\rceil+k}{n}\right\rceil\tag{5}\\ &=\sum_{k=0}^{n-1}\left(\left\lceil x+ \frac{k}{n}\right\rceil\right)\\ \end{align*}

which shows OP's claim is valid.

Comment:

• In (5) we use the identity $\sum_{k=0}^{n-1}\left\lceil \frac{\left\lceil y\right\rceil+k}{n}\right\rceil=\sum_{k=0}^{n-1}\left\lceil \frac {y+k}{n}\right\rceil$ for $y$ real, $k,n$ integer, $n$ positive.

Note: This example can be found besides many more interesting applications of floor and ceiling functions in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.