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"

m (→‎Hockey-Stick Identity)
(Another proof of the hockey stick identity)
Line 18: Line 18:
 
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 <math>\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}</math>
 +
Look at <math>\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}...+\binom{r+a}{r}</math>
 +
It can be rewritten as <math>\binom{r+1}{r+1}+\binom{r+1}{r}+\binom{r+2}{r}+...+\binom{r+a}{r}</math>
 +
Using pascals identity, we get <math>\binom{r+2}{r+1}+\binom{r+2}{r}+...\binom{r+a}{r}</math>
 +
We can continuously apply pascals identity until we get to
 +
<math>\binom{r+a}{r-1}+\binom{r+a}{r}=\binom{r+a+1}{r+1}</math>
  
 
==Vandermonde's Identity==
 
==Vandermonde's Identity==

Revision as of 20:19, 29 October 2006

This article is a stub. Help us out by expanding it.

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

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}$.

It can also be proven algebraicly with pascal's identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ Look at $\binom{r}{r}+\binom{r+1}{r}+\binom{r+2}{r}...+\binom{r+a}{r}$ It can be rewritten as $\binom{r+1}{r+1}+\binom{r+1}{r}+\binom{r+2}{r}+...+\binom{r+a}{r}$ Using pascals identity, we get $\binom{r+2}{r+1}+\binom{r+2}{r}+...\binom{r+a}{r}$ We can continuously apply pascals identity until we get to $\binom{r+a}{r-1}+\binom{r+a}{r}=\binom{r+a+1}{r+1}$

Vandermonde's Identity

Examples

See also

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