1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jared Mar 2 '15 at 8:16
  • $\begingroup$ 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. $\endgroup$ – Anjan3 Mar 2 '15 at 9:18
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Anjan3 Mar 2 '15 at 7:50
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.