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

Question

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.

I have no idea how to establish it. Can you please help me on this regard?

Thank you in advance

Answer 1

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

Answer 2

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

Answer 3

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