the binomial theorem

Question

the Question: Prove the critical Lemma we need to complete the proof of the Binomial Theorem:

i.e. prove $(^{n}_{k})=(^{n-1}_{k-1})+(^{n-1}_{k})$ for $0\lt k\lt n$ (this formula is known as Pascal’s Identity)

you can do this by a direct proof without using Induction.

Any help appreciated, I have no idea what it's talking about

You know the name of the identity,then why don't you google it? — rah4927, Apr 01 '14 at 06:05
ya i did that, and i'm betting copying a wikipedia version of the proof will get me less than 0 points and get me nowhere closer to understanding it — Mikky Davey, Apr 01 '14 at 06:10
,then instead of asking us how to prove a famous identity,why don't you cite the Wikipedia article and point out the specific parts you are having problems with? — rah4927, Apr 01 '14 at 06:13
See here.This page should give you some idea about what $_nC_k$ means and where factorials come from. — rah4927, Apr 01 '14 at 06:23

Kaj Hansen · Accepted Answer · 2014-04-01T06:28:00.517

1

Hint: Think about what $\binom{n}{k}$ means combinatorially.

Choose any one of the $n$ total elements at random. There are two cases: Either the element we have chosen is amongst the $k$-element subset, or it is not.

This method requires far less effort than non-combinatorial proofs, and a complete solution of this form can be found here:

http://www.math.uvic.ca/faculty/gmacgill/guide/combargs.pdf

edited Apr 01 '14 at 06:28

answered Apr 01 '14 at 06:07

Kaj Hansen

33,011

the proofs i've seen use a lot of factorials but they don't say where those factorials come from. I'm guessing there is some identity or something that our professor didn't give us or thought we knew? – Mikky Davey Apr 01 '14 at 06:13
@Mikky Davey,but isn't that how $_nC_k$ is computed?Anyway,Kaj_H's proof does not require the knowledge of factorials. – rah4927 Apr 01 '14 at 06:16
The method I suggest is quite simple and requires no factorials whatsoever. Simply think about what n-choose-k means combinatorially.
Since this is easily Googled, I will link to a complete solution using my method:

http://www.math.uvic.ca/faculty/gmacgill/guide/combargs.pdf
– Kaj Hansen Apr 01 '14 at 06:16
than you! that was extremely helpful – Mikky Davey Apr 01 '14 at 06:23

Alijah Ahmed · Answer 2 · 2014-04-01T06:26:44.907

1

Recall that

$${a \choose b}=\frac{a!}{b!(a-b)!}$$

and (for integer a)

$$a!=\prod_{k=1}^ak=a\times(a-1)\times(a-2)\times\cdots\times1$$

Starting from the right hand side

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

Can you take it from here?

edited Apr 01 '14 at 06:26

answered Apr 01 '14 at 06:20

Alijah Ahmed

11,609

score 0 · Answer 3 · answered Apr 01 '14 at 06:13

0

$\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}=\frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{1}{k}+\frac{1}{n-k}\right)$

$=\frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{n-k+k}{k(n-k)}\right)=\frac{(n-1)!}{(k-1)!(n-k-1)!}\frac{n}{k(n-k)}=\frac{(n-1)!.n}{(k-1)!.k.(n-k-1)!.(n-k)}=\frac{n!}{k(n-k)!}$

answered Apr 01 '14 at 06:13

kmitov

4,731

thank you for answering can you tell me what formula gives the factorials – Mikky Davey Apr 01 '14 at 06:15
By definition $n!=(n-1)!.n=1.2.3.4.5.\ldots.n$ – kmitov Apr 01 '14 at 06:19

the binomial theorem

3 Answers3