Difference between revisions of "The Nested Sum Theorem"

Latest revision as of 15:45, 6 January 2025

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 forms of this theorem, both obviously equivalent.

Nested Sum Theorem

Let $k$ be a arbitrary 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 an arbitrary 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 \}$

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

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$

Applications

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.

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)

@@ Line 6: / Line 6: @@
 ==Statement==
+There are two forms of this theorem, both obviously equivalent.
-There are two form of this theorem, both obviously equivalent.
 ===Nested Sum Theorem===
-Let <math>k</math> be a arbitary positive integer. Then,
+Let <math>k</math> be a arbitrary positive integer. Then,
 <cmath>\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}</cmath>
@@ Line 18: / Line 17: @@
 ===Lattice Point Theorem===
+Let <math>k</math> be an arbitrary positive integer. Then the <math>k</math> dimensional region
-Let <math>k</math> be a arbitary positive integer. Then the <math>k</math> dimensional region
+<cmath>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 \}</cmath>
-<cmath>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</cmath>
+contain <math>\dbinom{x_{k}+k-1}{k}</math> [[lattice points]].
-contain <math>\dbinom{x_{k}+k-1}{k}</math> [[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 <math>k</math> [[Distinguishability|indistinguishable]] objects, the number of ways to put it into <math>n</math> available spaces in a specific order is <math>\dbinom{n+k-1}{k}</math>. This interpretation is important for [[Combinatorics]].
 ==Proof==
 We proceed by induction.
@@ Line 54: / Line 47: @@
 The lattice point form of the theorem is obviously equivalent. <math>\square</math>
+==Applications==
+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 <math>k</math> [[Distinguishability|indistinguishable]] objects, the number of ways to put it into <math>n</math> available spaces in a specific order is <math>\dbinom{n+k-1}{k}</math>. This interpretation is important for [[Combinatorics]].
 ==Practice Problems==
@@ Line 60: / Line 56: @@
 ===Intermediate===
 * Suppose there is <math>m</math> hats and <math>n</math> bins to put them in, and all objects are assigned a corresponding integer. Suppose there is <math>x</math> ways of putting the hats in the bins such that the following criteria are followed:
@@ Line 67: / Line 62: @@
 (ii) There is at least one bin that contains at least two hats
-Find <math>x \mod 1000</math>. ([[Number Theory Problems Collection|Source and solution]])
+Find <math>x \mod 1000</math>. ([[Number Theory Problems Collection|Source]])
 ===Olympiad===
 ==See Also==
 * [[Number Theory Problems Collection]]
 * [[Hockey Stick Identity]]
 * [[Combinatorics]]
 [[Category:Theorems]]
+[[Category:Combinatorics]]
-[[Category:Combinatorics]]
+{{stub}}

Page

Toolbox

Search