Combinatorial identity

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

Vandermonde's Identity

Examples

AIME 2000II/7

Page

Toolbox

Search

Combinatorial identity

Contents

Hockey-Stick Identity

Proof

Vandermonde's Identity

Examples

See also