Difference between revisions of "Combinatorial identity"

(Hockey-Stick Identity)
Line 1: Line 1:
 
{{stub}}
 
{{stub}}
 
==Hockey-Stick Identity==
 
==Hockey-Stick Identity==
 +
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.
 +
 +
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.
 +
===Proof===
 +
This identity can be proven by induction on <math>n</math>.
 +
 +
<u>Base case</u>
 +
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>.
 +
 +
<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>.
 +
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>.
  
 
==Vandermonde's Identity==
 
==Vandermonde's Identity==

Revision as of 19:09, 29 August 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.

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

Vandermonde's Identity

Examples

See also

Invalid username
Login to AoPS