Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Combinatorial identity"

(→‎Vandermonde's Identity)
(→‎Proof)
Line 8: Line 8:
  
 
===Proof===
 
===Proof===
 +
 +
'''Inductive Proof'''
 +
 
This identity can be proven by induction on <math>n</math>.
 
This identity can be proven by induction on <math>n</math>.
  
−
<u>Base case</u>
+
<u>Base Case</u>
 
Let <math>n=r</math>.
 
Let <math>n=r</math>.
  
 
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.
 
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.
  
−
<u>Inductive step</u>
+
<u>Inductive Step</u>
 
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.
 
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.
 
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.
 
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.
  
−
It can also be proven algebraicly with pascal's identity
+
'''Algebraic Proof'''
−
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
+
 
−
Look at <math> {r \choose r}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}</math>
+
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.
−
It can be rewritten as <math> {r+1 \choose r+1}+{r+1 \choose r} +{r+2 \choose r}...+{r+a \choose r}</math>
+
Note that
−
Using pascals identity, we get <math>{r+2 \choose r+1}+{r+2 \choose r}+...+{r+a \choose r}</math>
+
 
−
We can continuously apply pascals identity until we get to
+
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
−
<math>{r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}</math>
+
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math>
 +
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.
 +
 
 +
'''Combinatorial Proof'''
 +
 
 +
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.
  
 
==Vandermonde's Identity==
 
==Vandermonde's Identity==

Revision as of 00:32, 11 February 2009

Hockey-Stick Identity

For $n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}$.

This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

Proof

Inductive Proof

This identity can be proven by induction on $n$.

Base Case Let $n=r$.

$\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}$.

Inductive Step Suppose, for some $k\in\mathbb{N}, k>r$, $\sum^k_{i=r}{i\choose r}={k+1\choose r+1}$. Then $\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}$.

Algebraic Proof

It can also be proven algebraically with Pascal's Identity, ${n \choose k}={n-1\choose k-1}+{n-1\choose k}$. Note that

${r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}$, which is equivalent to the desired result.

Combinatorial Proof

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are ${n+k-1\choose k-1}$ ways to do this. Alternatively, we can first give $0\le i\le n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, ${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$, which simplifies to the desired result.

Vandermonde's Identity

Vandermonde's Identity states that $\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r$, which can be proven combinatorially by noting that any combination of $r$ objects from a group of $m+n$ objects must have some $0\le k\le r$ objects from group $m$ and the remaining from group $n$.

Examples

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&oldid=30074"