How Do You Prove the Formula for n Choose k?

  • Topic:
  • Thread starter wittysoup
  • Start date
3 replies · 2K views · last reply
wittysoup
Messages
7
Reaction score
0
Hello all,

I need a little help with how to go about proving the following:
View attachment 619

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

For this, I have proceeded as follows:

Base case P(j):

View attachment 620

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.
 
Attachments
  • Handwritten identity: sum from i = j to n of binomial(i, j) equals binomial(n+1, j+1), written with binomial coefficients in stacked notation.
    sum_ichoosej.PNG
    1 KB · Views: 146
  • Handwritten-style equation: sum from i=j to j of binomial(i, j) = j!/(j!(j-j)!) = 0 = (j+1)!/((j+1)!((j+1)-(j+1))!), with the middle term reading 0.
    sum_basecase.PNG
    1.7 KB · Views: 123
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.
 
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)...

View attachment 621
 
Attachments
  • Handwritten-style derivation: sum from i=j to k+1 of binomial(i, j) equals sum from i=j to k of binomial(k+1, j+1) plus binomial(k+1+1, j), equals (k+1)! over (j+1)![(k+1)-(j+1)]! plus (k+2)! over (j)![(k+2)-(j)]!.
    k_plus1.PNG
    2.5 KB · Views: 141
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.