The Nested Sum Theorem

WARNING: This theorem is created by an untrustworthy person and is NOT verified. A mistake is very possible, and if you found it, please correct it as soon as you can.

This theorem is both The Nested Sum Theorem and The Lattice Point Theorem, so both pages redirect here.

The Nested Sum Theorem (otherwise known equivalently as the Lattice Point Theorem) is a theorem in Number Theory that describes the relation between nested sums and Combinatorics.

Statement

There are two form of this theorem, both obviously equivalent.

Nested Sum Theorem

Let $k$ be a arbitary positive integer. Then,

$\sum_{x_{k-1}=1}^{x_{k}} (\sum_{x_{k-2}=1}^{x_{k-1}} ( \dots \sum_{x_{1}=1}^{x_{2}} (\sum_{x=1}^{x_{1}} 1 )) \dots )) = \dbinom{x_{k}+k-1}{k}$

, where there is $k$ nested sums.

Lattice Point Theorem

Let $k$ be a arbitary positive integer. Then the $k$ dimensional region

$E= \{ (x, x_1, x_2, \dots , x_{k-1}) | 1 \le x \le x_1 \le x_2 \le \dots \le x_{k-1} \le x_k \} , x_i \in Z$

contain $\dbinom{x_{k}+k-1}{k}$ Lattice points.

This theorem in its different forms is very useful. The summation form is useful for algebra. The lattice point form is useful for geometry involving lattice points. Another interpretation of the theorem is that for $k$ indistinguishable objects, the number of ways to put it into $n$ available spaces in a specific order is $\dbinom{n+k-1}{k}$ . This interpretation is important for Combinatorics.

Proof

We proceed by induction.

The base case, $k=1$ is obvious, since

$\sum_{i=1}^{n} (1) = n= \dbinom{n}{1}$

Suppose the theorem holds for $k$ , so that

$\sum_{x_{k-1}=1}^{x_{k}} (\sum_{x_{k-2}=1}^{x_{k-1}} ( \dots \sum_{x_{1}=1}^{x_{2}} (\sum_{x=1}^{x_{1}} 1 )) \dots )) = \dbinom{x_{k}+k-1}{k}$

where there is $k$ summations.

Then,

$\sum_{x_{k}=1}^{x_{k+1}} (\sum_{x_{k-1}=1}^{x_{k}} ( \dots \sum_{x_{1}=1}^{x_{2}} (\sum_{x=1}^{x_{1}} 1 )) \dots )) = \sum_{x_{k}=1}^{x_{k+1}} (\dbinom{x_{k}+k-1}{k})$

$=\dbinom{x_{k+1}+k}{k+1}$

by the Hockey Stick Identity.

The result follow from induction.

The lattice point form of the theorem is obviously equivalent. $\square$

Practice Problems

Introductory

Intermediate

Suppose there is $m$ hats and $n$ bins to put them in, and all objects are assigned a corresponding integer. Suppose there is $x$ ways of putting the hats in the bins such that the following criteria are followed:

(i) If $i<j$ (where $i$ and $j$ are integers), then hat $i$ is placed in a bin whose number is less than or equal to the number of the bin that hat $j$ is placed in

(ii) There is at least one bin that contains at least two hats

Find $x \mod 1000$ . (Source and solution)

Page

Toolbox

Search