Intereting Posts

Immersion, embedding and category theory
How to show $\lim_{x \to 1} \frac{x + x^2 + \dots + x^n – n}{x – 1} = \frac{n(n + 1)}{2}$?
$ \cos {A} \cos {B} \cos {C} \leq \frac{1}{8} $
Why is there apparently no general notion of structure-homomorphism?
How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $
Legendre's Proof (continued fractions) from Hardy's Book
Euler's theorem: ^2014^2014 mod 98
Calculate a limit $\lim_{x \to \pi/2} \frac{\sqrt{ \sin x} – \sqrt{ \sin x}}{\cos^2x}$
What is an intuition behind total differential in two variables function?
On the general form of the family $\sum_{n=1}^\infty \frac{n^{k}}{e^{2n\pi}-1} $
Quadratic residues and representations of integers by a binary quadratic form
Hilbert's Nullstellensatz without Axiom of Choice
Show that $e^{x+y}=e^xe^y$ using $e^x=\lim_{n\to\infty }\left(1+\frac{x}{n}\right)^n$.
Primes for which $x^k\equiv n\pmod p$ is solvable: the fixed version
Show that $m\mathbb{Z}/md\mathbb{Z} \cong \mathbb{Z}/d\mathbb{Z}$ if and only if $(d,m)=1$

After reading this question, the most popular answer use the identity

$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$

What’s the name of this identity? Is it the identity of the Pascal’s triangle modified.

How can we prove it? I tried by induction, but without success. Can we also prove it algebraically?

- Product of binomial coefficient as a basis
- Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$
- Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction
- when is $\frac{1}{n}\binom{n}{r}$ an integer
- How to show that this binomial sum satisfies the Fibonacci relation?
- Xmas Combinatorics 2014

Thanks for your help.

**EDIT 01 :** 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.

- Generating functions and central binomial coefficient
- Combinations of 6 students among 20, at least one male
- Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
- Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$
- Simplify the expression $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k}{k}$
- Divisibility question
- Show that ${n \choose k}\leq n^k$
- Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
- How many different combinations of a six sided die rolls equals n
- Vandermonde-like identities

This is purely algebraic. First of all, since $\dbinom{t}{k} =0$ when $k>t$ we can rewrite

$$\binom{n+1}{k+1} = \sum_{t=0}^{n} \binom{t}{k}=\sum_{t=k}^{n} \binom{t}{k}$$

Recall that (by the Pascal’s Triangle),

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Hence

$$\binom{t+1}{k+1} = \binom{t}{k} + \binom{t}{k+1} \implies \binom{t}{k} = \binom{t+1}{k+1} – \binom{t}{k+1}$$

Let’s get this summed by $t$:

$$\sum_{t=k}^{n} \binom{t}{k} = \sum_{t=k}^{n} \binom{t+1}{k+1} – \sum_{t=k}^{n} \binom{t}{k+1}$$

Let’s factor out the last member of the first sum and the first member of the second sum:

$$\sum _{t=k}^{n} \binom{t}{k}

=\left( \sum_{t=k}^{n-1} \binom{t+1}{k+1} + \binom{n+1}{k+1} \right)

-\left( \sum_{t=k+1}^{n} \binom{t}{k+1} + \binom{k}{k+1} \right)$$

Obviously $\dbinom{k}{k+1} = 0$, hence we get

$$\sum _{t=k}^{n} \binom{t}{k}

=\binom{n+1}{k+1}

+\sum_{t=k}^{n-1} \binom{t+1}{k+1}

-\sum_{t=k+1}^{n} \binom{t}{k+1}$$

Let’s introduce $t’=t-1$, then if $t=k+1 \dots n, t’=k \dots n-1$, hence

$$\sum_{t=k}^{n} \binom{t}{k}

= \binom{n+1}{k+1}

+\sum_{t=k}^{n-1} \binom{t+1}{k+1}

-\sum_{t’=k}^{n-1} \binom{t’+1}{k+1}$$

The later two arguments eliminate each other and you get the desired formulation

$$\binom{n+1}{k+1}

= \sum_{t=k}^{n} \binom{t}{k}

= \sum_{t=0}^{n} \binom{t}{k}$$

Imagine the first $n + 1$ numbers, written in order on a piece of paper. The right hand side asks in how many ways you can pick $k+1$ of them. In how many ways can you do this?

You first pick a highest number, which you circle. Call it $s$. Next, you still have to pick $k$ numbers, each less than $s$, and there are $\binom{s – 1}{k}$ ways to do this.

Since $s$ is ranging from $1$ to $n$, $t:= s-1$ is ranging from $0$ to $n$ as desired.

$$\begin{align}

\sum_{t=\color{blue}0}^n \binom{t}{k} =\sum_{t=\color{blue}k}^n\binom tk&= \sum_{t=k}^n\left[ \binom {t+1}{k+1}-\binom {t}{k+1}\right]\\

&=\sum_{t=\color{orange}k}^\color{orange}n\binom {\color{orange}{t+1}}{k+1}-\sum_{t=k}^n\binom t{k+1}\\

&=\sum_{t=\color{orange}{k+1}}^{\color{orange}{n+1}}\binom {\color{orange}{t}}{k+1}-\sum_{t=k}^n\binom t{k+1}\\

&=\binom{n+1}{k+1}-\underbrace{\binom k{k+1}}_0&&\text{by telescoping}\\

&=\binom{n+1}{k+1}\quad\blacksquare\\

\end{align}$$

We can use the well known identity

$$1+x+\dots+x^n = \frac{x^{n+1}-1}{x-1}.$$

After substitution $x=1+t$ this becomes

$$1+(1+t)+\dots+(1+t)^n=\frac{(1+t)^{n+1}-1}t.$$

Both sides of these equations are polynomials in $t$. (Notice that the RHS simplifies to $\sum_{j=1}^{n+1}\binom {n+1}j t^{j-1}$.)

If we compare coefficient of $t^{k}$ on the LHS and the RHS we see that

$$\binom 0k + \binom 1k + \dots + \binom nk = \binom{n+1}{k+1}.$$

This proof is basically the same as the proof using generating functions, which was posted in other answers. However, I think it is phrased a bit differently. (And if it is formulated this way, even somebody who has never heard of generating functions can follow the proof.)

You can use induction on $n$, observing that

$$

\sum_{t=0}^{n+1} \binom{t}{k}

= \sum_{t=0}^{n} \binom{t}{k} + \binom{n+1}{k}

= \binom{n+1}{k+1} + \binom{n+1}{k}

= \binom{n+2}{k+1}

$$

The RHS is the number of $k+1$ subsets of $\{1,2,…,n+1\}$. Group them according to the largest element in the subset. Sum up all the cases. Get the LHS.

Another technique is to use snake oil. Call your sum:

$\begin{align}

S_k

&= \sum_{0 \le t \le n} \binom{t}{k}

\end{align}$

Define the generating function:

$\begin{align}

S(z)

&= \sum_{k \ge 0} S_k z^k \\

&= \sum_{k \ge 0} z^k \sum_{0 \le t \le n} \binom{t}{k} \\

&= \sum_{0 \le t \le n} \sum_{k \ge 0} \binom{t}{k} z^k \\

&= \sum_{0 \le t \le n} (1 + z)^t \\

&= \frac{(1 + z)^{n + 1} – 1}{(1 + z) – 1} \\

&= z^{-1} \left( (1 + z)^{n + 1} – 1 \right)

\end{align}$

So we are interested in the coefficient of $z^k$ of this:

$\begin{align}

[z^k] z^{-1} \left( (1 + z)^{n + 1} – 1 \right)

&= [z^{k + 1}] \left( (1 + z)^{n + 1} – 1 \right) \\

&= \binom{n + 1}{k + 1}

\end{align}$

We can use the integral representation of the binomial coefficient $$\dbinom{t}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{t}}{z^{k+1}}dz\tag{1}

$$ and get $$\sum_{t=0}^{n}\dbinom{t}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\sum_{k=0}^{n}\left(1+z\right)^{t}}{z^{k+1}}dz

$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(z+1\right)^{n+1}}{z^{k+2}}dz-\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{1}{z^{k+2}}dz

$$ and so usign again $(1)$ we have $$\sum_{t=0}^{n}\dbinom{t}{k}=\dbinom{n+1}{k+1}-0=\color{red}{\dbinom{n+1}{k+1}.}$$

- The interchange of limit for integration
- Elementary proof for $\sqrt{p_{n+1}} \notin \mathbb{Q}(\sqrt{p_1}, \sqrt{p_2}, \ldots, \sqrt{p_n})$ where $p_i$ are different prime numbers.
- A trigonometic integral with complex technicals
- Find a solution of the polynomial
- What is the definition of a complex manifold with boundary?
- What are the odds of getting heads 7 times in a row in 40 tries of flipping a coin?
- Is there a way to determine how many digits a power of 2 will contain?
- What math should a computer scientist take in college?
- Vanishing of the first Chern class of a complex vector bundle
- Bubble sorting question
- Proving completeness of a metric space
- Expected number of frog jumps
- Are $X$ and $X+Y$ independent, if $X$ and $Y$ are independent?
- Can the number of numbers in two intervals over $\mathbb{R^+}$ be compared?
- Fast exponentiation algorithm – How to arrive at it?