# How to prove this identity of ceiling function?

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?

• Shouldn't it be something like $\lceil nx\rceil + n-1$ instead of $\lceil x\rceil + n-1$ ? The formula seems false for $n=3$ and $x=10000$ – GBQT Aug 17 '15 at 14:19
• @GBQT: I don't know, sir; I really copied what my book wrote; maybe the book mistook:( – user142971 Aug 17 '15 at 14:23
• Note that the left side is about $nx$, while the right is about $x$, so it cannot be right – Ross Millikan Aug 17 '15 at 14:23
• @Ross Millikan: Sir, can you refer me any site that deduces it? BTW, is there any special name for this like "Hermite's Identity" for floor functions? – user142971 Aug 17 '15 at 15:51

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

• Nice approach! But shouldn't you have $\lceil nx+1\rceil$ when you evaluate $f(x+1/n)$? I think that would change the picture here... – bartgol Aug 17 '15 at 16:38
• I think the lest term of $f\left(x+\frac1n\right)$ has a typo. – user142971 Aug 17 '15 at 16:38
• @bartgol: You came first by ~3 sec!! – user142971 Aug 17 '15 at 16:39
• @user36790 Basically, if a function has a period $T$, then studying it over $[0,T)$ (or $(0,T]$, $[a,a+T)$, etc.) is enough to calculate it over all of $\Bbb R$.  In this case, we have $T=1/n$ and we know that if $x\in (0,T]$, then $f(x)$ is equal to $n-1$. So if $x\in (T,2T]$, then $f(x) = f(x-T) = n-1$. If $x\in (2T,3T]$, then $f(x)=f(x-2T)=n-1$ and so on. So we know that $f(x) = n-1$ for all $x\in(0,\infty)$. The same thing can be done for $(\infty,0]$ – Kitegi Aug 17 '15 at 16:56
• @user36790 Well, since $x\in(0,\frac1n]$, then $x,x+\frac1n,\dots,x+1-\frac1n$ and $nx$ are all in $(0,1]$, so their $\lceil\ \rceil$ is equal to $1$. So we get $f(x)=(1+1+\dots+1) -1=n-1$ – Kitegi Aug 17 '15 at 17:06

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.

• Sir, firstly, thanks for answering but can you please elaborate how you wrote ${(k-1) \over n}\lt x\le {k\over n}$? Also, can you please explain the line "The same general property allows us to assume that $0<x≤1$"? Thanks in advance:) – user142971 Aug 17 '15 at 16:24
• @user36790, there are $n$ terms on the left hand side, so if $x$ is shifted by an integer amount $m$, that side shifts by $nm$, while on the right hand side, $\lceil n(x+m)\rceil=\lceil nx+nm\rceil]=\lceil nx\rceil+nm$. Once you have $x$ between $0$ and $1$, you know it lies between some pair of consecutive multiples of the fraction $1/n$, with the upper multiple at most $n/n$. – Barry Cipra Aug 17 '15 at 17:20

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

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.