Difference between revisions of "Combinatorial identity"

Revision as of 20: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

AIME 2000II/7

@@ Line 1: / Line 1: @@
 {{stub}}
 ==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==

Page

Toolbox

Search