Welcome to our community

Be a part of something great, join today!

Inductive proof

wittysoup

New member
Feb 13, 2013
7
Hello all,

I need a little help with how to go about proving the following:
sum_ichoosej.PNG

the formula for n choose k is n!/(k!(n-k)!)

For this, I have proceeded as follows:

Base case P(j):

sum_basecase.PNG

I am not sure if this is correct... but the next step would be to Assume P(k), I get stuck at that step because the algebraic expression does not look right... Am I going about this the right way? Thanks.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Your base case $P_j$ would be:

$\displaystyle \sum_{i=j}^j{i \choose j}={j \choose j}=1={j+1 \choose j+1}$

This is true.

Next, state the induction hypothesis $P_k$:

$\displaystyle \sum_{i=j}^k{i \choose j}={k+1 \choose j+1}$

I think my inductive step would be to add ${k+1 \choose j}$ to both sides:

$\displaystyle \sum_{i=j}^k{i \choose j}+{k+1 \choose j}={k+1 \choose j+1}+{k+1 \choose j}$

$\displaystyle \sum_{i=j}^{k+1}{i \choose j}={k+1 \choose j+1}+{k+1 \choose j}$

Now, what you need to do is show that:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}={(k+1)+1 \choose j+1}$

Essentially, you need to prove Pascal's identity. Use the definition of the binomial coefficients to do so, and if you get stuck, we can offer further guidance.
 

wittysoup

New member
Feb 13, 2013
7
Thanks for that, it seems like I miscalculated the first result... I am now stuck here, being that I do not know how to simplify this ( I actually worked out further on paper trying to get a common denominator)...

k_plus1.PNG
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
I would state:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+1)!}{(j+1)!((k+1)-(j+1))!}+\frac{(k+1)!}{j!((k+1)-j)!}$

Simplify a bit:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+1)!}{(j+1)!(k-j)!}+\frac{(k+1)!}{j!(k+1-j)!}$

Next, factor:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+1)!}{j!(k-j)!}\left(\frac{1}{j+1}+\frac{1}{k+1-j} \right)$

Combine terms within parentheses:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+1)!}{j!(k-j)!}\left(\frac{k+1-j+j+1}{(j+1)(k+1-j)} \right)$

Combine like terms:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+1)!}{j!(k-j)!}\left(\frac{k+2}{(j+1)(k+1-j)} \right)$

Combine factors:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}=\frac{(k+2)!}{(j+1)!(k+1-j)!}$

Rewrite right side as binomial coefficient:

$\displaystyle {k+1 \choose j+1}+{k+1 \choose j}={(k+1)+1 \choose j+1}$

Thus, using this result in our inductive step, we obtain:

$\displaystyle \sum_{i=j}^{k+1}{i \choose j}={(k+1)+1 \choose j+1}$

We have derived $P_{k+1}$ from $P_k$ thereby completing the proof by induction.