Difference between revisions of "The Nested Sum Theorem"
(Created page with "'''WARNING:''' This theorem is created by a untrustworthy person and is NOT verified. A mistake is very possible, and if you found it, please correct it as soon as possible....") |
m (Formatting) |
||
| (5 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | '''WARNING:''' This theorem is created by | + | '''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.'' | ''This theorem is both [[The Nested Sum Theorem]] and [[The Lattice Point Theorem]], so both pages redirect here.'' | ||
| Line 6: | Line 6: | ||
==Statement== | ==Statement== | ||
| + | There are two forms of this theorem, both obviously equivalent. | ||
===Nested Sum Theorem=== | ===Nested Sum Theorem=== | ||
| − | Let <math>k</math> be a | + | 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> | <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 16: | Line 17: | ||
===Lattice Point Theorem=== | ===Lattice Point Theorem=== | ||
| + | Let <math>k</math> be an arbitrary 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> | |
| − | + | contain <math>\dbinom{x_{k}+k-1}{k}</math> [[lattice points]]. | |
| − | |||
| − | contain <math>\dbinom{x_{k}+k-1}{k}</math> [[ | ||
| − | |||
| − | |||
| − | |||
| − | |||
==Proof== | ==Proof== | ||
| − | |||
We proceed by induction. | We proceed by induction. | ||
| Line 45: | Line 40: | ||
<cmath>\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})</cmath> | <cmath>\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})</cmath> | ||
| − | <cmath>=\dbinom{x_{k+1}+k}{k+1 | + | <cmath>=\dbinom{x_{k+1}+k}{k+1}</cmath> |
by the [[Hockey Stick Identity]]. | by the [[Hockey Stick Identity]]. | ||
| Line 52: | Line 47: | ||
The lattice point form of the theorem is obviously equivalent. <math>\square</math> | 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== | ==Practice Problems== | ||
| Line 58: | Line 56: | ||
===Intermediate=== | ===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: | |
| − | * 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 | ||
(i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in | (i) If <math>i<j</math> (where <math>i</math> and <math>j</math> are integers), then hat <math>i</math> is placed in a bin whose number is less than or equal to the number of the bin that hat <math>j</math> is placed in | ||
| Line 65: | Line 62: | ||
(ii) There is at least one bin that contains at least two hats | (ii) There is at least one bin that contains at least two hats | ||
| − | Find <math>x \mod 1000</math>. ([[Number Theory Problems Collection|Source | + | Find <math>x \mod 1000</math>. ([[Number Theory Problems Collection|Source]]) |
===Olympiad=== | ===Olympiad=== | ||
| + | |||
==See Also== | ==See Also== | ||
| − | |||
* [[Number Theory Problems Collection]] | * [[Number Theory Problems Collection]] | ||
| + | * [[Hockey Stick Identity]] | ||
| + | * [[Combinatorics]] | ||
| − | + | [[Category:Theorems]] | |
| + | [[Category:Combinatorics]] | ||
| − | + | {{stub}} | |
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.
Contents
Statement
There are two forms of this theorem, both obviously equivalent.
Nested Sum Theorem
Let 
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}\]](http://latex.artofproblemsolving.com/9/5/f/95f8d9ccdd6d7a339fe3ae148c979da1ef396583.png)
, where there is nested sums.
Lattice Point Theorem
Let be an arbitrary positive integer. Then the 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 \}\]](http://latex.artofproblemsolving.com/2/2/d/22d05083cb32ede2d5ba53b646ce9bdd7f8896d3.png)
contain 
lattice points.
Proof
We proceed by induction.
The base case, 
is obvious, since
![\[\sum_{i=1}^{n} (1) = n= \dbinom{n}{1}\]](http://latex.artofproblemsolving.com/f/5/8/f589786a5ae10b03ae9b3585aa36fab6889f51ca.png)
Suppose the theorem holds for , so that
where there is 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})\]](http://latex.artofproblemsolving.com/7/e/2/7e2cc72b180af74a561912c7db3675547b8a1298.png)
![\[=\dbinom{x_{k+1}+k}{k+1}\]](http://latex.artofproblemsolving.com/a/a/2/aa25e1c5a9eb958043965af3de6f7d6129766a30.png)
by the Hockey Stick Identity.
The result follow from induction.
The lattice point form of the theorem is obviously equivalent. 
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 indistinguishable objects, the number of ways to put it into 
available spaces in a specific order is 
. This interpretation is important for Combinatorics.
Practice Problems
Introductory
Intermediate
- Suppose there is
hats and 
bins to put them in, and all objects are assigned a corresponding integer. Suppose there is 
ways of putting the hats in the bins such that the following criteria are followed:
hats and 
ways of putting the hats in the bins such that the following criteria are followed:(i) If 
(where 
and 
are integers), then hat is placed in a bin whose number is less than or equal to the number of the bin that hat is placed in
(ii) There is at least one bin that contains at least two hats
Find 
. (Source)
Olympiad
See Also
This article is a stub. Help us out by expanding it.
