Binomials!

Probability Level 3

$\large \sum_{j=l}^m C(j,l)$

Let $C(j,l)$ denote the binomial coefficient, $\frac{j!}{l!(j-l)!}$ . For integers $m\geq l \geq 0$ , what is the value of the summation above?

C(m+1,l)

C(m+2,l+1)

C(m+1,l+1)

C(m,l+1)

1 solution

Venkata Karthik Bandaru
Jun 9, 2015

PROOF BY INDUCTION

Let $P(m)$ be the proposition " $\sum_{j=l}^m C(j,l) = C(m+1,l+1)$ ." Then,

Base Step : $P(l)$ is true. [ Because C(l,l)=C(l+1,l+1)=1 ]

Inductive Step : Let P(k) be true for some integer $k \geq l$ . Now we need to prove from this that $P(k+1)$ is true.So, we have from the inductive hypothesis

$C(l,l) + C(l+1,l) + C(l+2,l) + .... + C(k,l) = C(k+1,l+1)$

$\Rightarrow C(l,l) + C(l+1,l) + .... + C(k,l) + C(k+1,l) = C(k+1,l+1) + C(k+1, l) = C(k+2,l+1)$ [ From Pascal's identity $C(n,r) + C(n,r-1) = C(n+1,r)$ ]

$= C([k+1]+1, l+1) \Rightarrow P(k+1)$ true.

Hence, the proof is now complete by First Principle of Mathematical Induction.

This is something that our teacher at JEE coaching institute said to mug up...😂😂😂

A Former Brilliant Member - 3 years, 2 months ago

It can be treated as a coefficient in a GP (see it?). I didn't know this when I wrote the solution.

Venkata Karthik Bandaru - 3 years, 2 months ago

Binomials!

1 solution

0 pending reports