pascal proof

perusal

New member
Joined
Jan 7, 2019
Messages
48
I am having trouble constructing a proof by induction for the following.

[MATH] \binom{n}{r} = \frac{n!}{r!(n-r)!} [/MATH]
I was wondering if anyone would be kind enough to help me out?
 
Why do you want to prove it by induction? Please tell us the context of your question, as requested here. In any case, we want to see what you have tried so far, so we can see what sort of help you need.

I expect that context to include some hints as to how you are expected to do it, such as "induction on which variable?"

But with no context, I'd start by establishing what definition you are using for the LHS, such that you would be able to relate different binomial coefficients to one another. For example, what happens when you increase n, or r, by 1? Then you'd want to relate that to what happens on the RHS.
 
It could be ... or it could be defined as a certain coefficient of a binomial expansion, or as a number of combinations, or maybe something else. In any case, a proof can't be considered until we know what it means in context.
 
Can you send your solution here so I can asses if you have really understood this lesson or formula? I can give you an answer right now but I want you to fully understand this and be capable of doing this easier in the future. I'm just like you in the past and Its not a bad thing, but what I did though is hire maths tutors. ;)
 
Last edited by a moderator:
Sorry; I will give you a little more detail.
So I have the definition

[MATH] \binom{n + 1}{r} = \binom{n}{r} + \binom{n}{r-1} [/MATH]
and I gathered that I could manipulate one side of the equation to make it equal to the other that would be my proof by induction.

So it tried manipulating the right side like so:

[MATH] \frac{(n+1)!}{r!(n+1-r)!} + \frac{(n+1)!}{(r-1)!(n-(r-1))!} [/MATH]
and worked with that for about half an hour but couldn't make the two sides of the equations equate.

I figure I am either just not approaching the question correctly or there is some element of factorial manipulation that I am unaware of.
 
Sorry; I will give you a little more detail.
So I have the definition

[MATH] \binom{n + 1}{r} = \binom{n}{r} + \binom{n}{r-1} [/MATH]
and I gathered that I could manipulate one side of the equation to make it equal to the other that would be my proof by induction.

So it tried manipulating the right side like so:

[MATH] \frac{(n+1)!}{r!(n+1-r)!} + \frac{(n+1)!}{(r-1)!(n-(r-1))!} [/MATH]
and worked with that for about half an hour but couldn't make the two sides of the equations equate.

I figure I am either just not approaching the question correctly or there is some element of factorial manipulation that I am unaware of.
For the RHS -

why do you have (n+1)! in the numerator?

It should be n!

Please share your work, so that we can catch any mistake (if present).
 
I agree with SK's diagnosis.

Just for clarity, it appears that you are using a recursive definition of the binomial coefficient, which I suppose is something like

[MATH]\binom{r}{r} = 1[/MATH]​
[MATH]\binom{n + 1}{r} = \binom{n}{r} + \binom{n}{r-1}[/MATH] for [MATH]n \gt r[/MATH].​

This differs from the recursive definition I find, for example, in Wikipedia. I was probably expecting you to want an inductive proof of the binomial theorem, which seems more natural. But you do what you were told to do ...

The only part of the proof you are struggling with is the inductive step. Correct?
 
maths.jpg

Thanks you for your help everyone. I have attached the original question for clarity.
 
I probably should have recognized from your use of "Pascal" in the title that you are starting fro Pascal's triangle itself as the definition; that implies other recursion formulas besides the one quoted, but we can infer that you are expected to use that one (together with other information) for your proof.

Did you complete the proof, or do you need additional help? If so, we'll want to see what you've done again.
 
I probably should have recognized from your use of "Pascal" in the title that you are starting fro Pascal's triangle itself as the definition; that implies other recursion formulas besides the one quoted, but we can infer that you are expected to use that one (together with other information) for your proof.

Did you complete the proof, or do you need additional help? If so, we'll want to see what you've done again.
maths.jpg
 
Rather than changing the numerators first, how about first making a common denominator, so you can add the fractions and get the single fraction on the LHS that you are aiming for? Things will be a little simpler that way.

You'll be using facts like r! = r(r-1)! .

You haven't actually shown the induction process, but I assume this step is part of a fuller answer you are working on.
 
Rather than changing the numerators first, how about first making a common denominator, so you can add the fractions and get the single fraction on the LHS that you are aiming for? Things will be a little simpler that way.

You'll be using facts like r! = r(r-1)! .

You haven't actually shown the induction process, but I assume this step is part of a fuller answer you are working on.


maths.png

It think that is it. The think that I was missing was that n-(r-1) is equal to n+1-r. Once I realised that, it became quite simple. Thanks for your help.
 
Looks good.

I did it with less work, by using that key fact earlier and obtaining the target denominator immediately:

[MATH]\frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-(r+1))!} = \frac{n!(n-r+1)}{r!(n-r)!(n-r+1)} + \frac{n!(r)}{(r-1)!(n-r+1)!(r)} =[/MATH]​
[MATH]\frac{n!(n-r+1)}{r!(n-r+1)!} + \frac{n!r}{r!(n-r+1)!} = \frac{n!(n-r+1) + n!r}{r!(n-r+1)!} = \frac{n!(n+1)}{r!(n-r+1)!} = \frac{(n+1)!}{r!(n+1-r)!}[/MATH]​

But that's equivalent to what you did.
 
Top