Proof for Concrete Mathematics 3.24

Question

I'm reading Concrete Mathematics by Graham, Knuth, Patashnik . I found that for every integer $n$, this holds : $$n = \lceil n/m \rceil + \lceil (n-1)/m \rceil + \cdots + \lceil (n-m+1)/m \rceil$$

I don't understand that! why this is true? Is there any name for this property?

Answer 1

To prove: $$n = \lceil n/m \rceil + \lceil (n-1)/m \rceil + \cdots + \lceil (n-m+1)/m \rceil$$ as Hagen suggests, do induction on $n$.

For $n,m \in \mathbb{Z}$, with the restrictions that $n \neq 0$ and $m>0$, we have two cases: $n$ positive, and $n$ negative.

The equation for $n=1$ holds:

$$n = \lceil 1/m \rceil + \lceil 0/m \rceil + \cdots + \lceil (2-m)/m \rceil \\ = 1 + 0 + 0 \cdots + 0 = 1.$$

The third and following terms on the right hand side are zero because all of the arguments to the ceiling function are greater than $-1$ but less than $0$.

Assuming it holds for $n=k$:

$$k = \lceil k/m \rceil + \lceil (k-1)/m \rceil + \cdots + \lceil (k-m+1)/m \rceil,$$

then we can see that it holds for $n=k+1$:

$$k+1 = \lceil (k+1)/m \rceil + \lceil (k)/m \rceil + \cdots + \lceil (k-m+2)/m \rceil \\ = k + \lceil (k+1)/m \rceil - \lceil (k-m+1)/m \rceil \\ = k + \lceil (k+1)/m \rceil - (\lceil (k+1)/m \rceil - 1) = k+1.$$

A similar induction can be done for negative $n$ to complete the proof.

Answer 2

This is certainly not as slick and neato as induction,
but it is a bit more simple minded.
Just counting ...


For exactly one k, n-m+1<=k<=n, k/m is integral.
That is, floor(k/m) = ceiling(k/m).
For all i, n-m+1<=i<=k, ceiling(i/m) = k/m.
For all j, k<j<=n, ceiling(j/m) = k/m + 1.
There are m terms in the sum,
 so there are m such i's and j's together
 and exactly n-k such j's.

So, ceiling(n/m) + ceiling((n−1)/m) +  ⋯ + ceiling((n−m+1)/m)
 = m(k/m) + (n-k)1
 = n

Answer 3

There are already two good answers, but I think that, to gain insight into what's going on, you would do well to look at a few examples with reasonable values of $n$ and $m$. By "reasonable," I mean not so small that things become trivial and not so large that the calculation becomes a chore; try some examples like $n=12$ and $m=5$. I think that, if you work out a few such examples, you'll see what's going on. (If you can see what's going on easily by reading fbaggins's answer, then ignore mine.)