# How to show $u_n=\binom{n}{l}\Rightarrow s_n=\binom{n+1}{l+1}$?

Hello respected everyone.

Before I ask my query, let us first define binomial coeffcients as follows:

For $n, r\in \mathbb N$, we define $$\binom{n}{r}=\begin{cases} \frac{n!}{r!(n-r)!}~~~ \text{if} ~~~0\leq r\leq n\\ 0~~~~~~~~~~~~~ \text{otherwise} \end{cases}$$ which means for $\binom{5}{3}, \binom{5}{5}$ etc we shall consider the usual computation of ${}^nC_r$ but for expression like $\binom{5}{6}, \binom{3}{8}$ etc we shall simply write $0$. Note that we are considering $\binom{n}{0}=1$ as convention, $n\in \mathbb N$.

I was trying to prove the following: $\sum_{i=1}^n \binom{i}{l}=\binom{n+1}{l+1}$. Actually I have considered a sequence $\{u_n\}$ where $u_n=\binom{n}{l}$ for $n,l\in \mathbb N$. And I am trying to show that $s_n=\sum_{i=1}^n u_i=\binom{n+1}{l+1}$ under the definition of $\binom{n}{r}$ given above.

The reverse direction viz $s_n=\binom{n+1}{l+1}\Rightarrow u_n=\binom{n}{l}$ was easy to establish by using $s_{n}-s_{n-1}=u_n$. But I got stuck in the forward proof.

• Well the very first thing is to change your sum, instead of $\sum_1^n \binom{i}{l}$, you should have: $\sum_{l}^n \binom{i}{l}$ (so we always assume that $n \geq l$. – Jared Mar 2 '15 at 8:16
• Its really remarkable the way both the solution below have been provided. I have no idea which should I consider the best. :) Both are innovative. – Anjan3 Mar 2 '15 at 9:18

From $$\binom{n}{l} + \binom{n}{l+1} = \binom{n+1}{l+1}$$ follow that $$\binom{n}{l}= \binom{n+1}{l+1}-\binom{n}{l+1}$$ or $$\sum_{i=1}^n\binom{i}{l}=\sum_{i=0}^n\binom{i}{l}=\sum_{i=0}^n\binom{i+1}{l+1}-\binom{i}{l+1}=$$ $$=\sum_{i=1}^{n+1}\binom{i}{l+1}-\sum_{i=1}^n\binom{i}{l+1}=$$ $$=\binom{n+1}{l+1}+\sum_{i=1}^{n}\binom{i}{l+1}-\sum_{i=1}^n\binom{i}{l+1}=\binom{n+1}{l+1}$$

hint: $\binom{n}{l} + \binom{n}{l+1} = \binom{n+1}{l+1}$

• What I am asking to establish is $\binom{1}{l}+\binom{2}{l}+\cdots+\binom{n}{l}=\binom{n+1}{l+1}$. How that hint will be used here please ? – Anjan3 Mar 2 '15 at 7:50

Try proving by induction:

Base Case: $n = l$

For $n = l$, the sum is simply $\sum_l^l \binom{i}{l} = \binom{l}{l} = 1$. Indeed for this base case $\binom{n + 1}{l + 1} = \binom{l + 1}{l + 1} = 1$.

Inductive Step: Show that if $\sum_l^{n - 1} \binom{i}{l} = \binom{n}{l + 1}$ then $\sum_l^n \binom{i}{l} = \binom{n + 1}{l + 1}$

According to the inductive hypothesis, $\sum_l^{n - 1}\binom{i}{l} = \binom{n}{i + 1}$:

$$\binom{n}{l + 1} = \frac{n!}{(l + 1)!(n - l - 1)!}$$

Now we add $\binom{n}{l} = \frac{n!}{l!(n - l)!}$ to find the $\sum_l^n \binom{i}{l}$:

\begin{align} \sum_l^n \binom{i}{l} = &\ \sum_l^{n - 1}\binom{i}{l} + \binom{n}{l}\\ =&\ \frac{n!}{(l + 1)!(n - l - 1)!} + \frac{n!}{l!(n - l)!} \\ =&\ \frac{n!(n - l)}{(l+1)l!(n - l)!} + \frac{n!}{l!(n - l)!} \\ =&\ \frac{n!}{l!(n - l)!}\left(\frac{n - l}{l + 1} + 1\right) \\ =&\ \frac{n!}{l!(n - l)!}\frac{n - l + l + 1}{l + 1} \\ =&\ \frac{n!}{l!(n - l)!}\frac{n + 1}{l + 1} \\ =&\ \frac{(n +1)!}{(l+1)!(n - l)!} \end{align}

You can verify that this is indeed:

$$\binom{n + 1}{l+1} = \frac{(n + 1)!}{(l+1)!(n + 1 - (l + 1))!} = \frac{(n + 1)!}{(l+1)!(n - l)!}$$

Therefore this formula is true because it's true for $n = l$ and it remains true when we increment $n$.