Pascal's triangle where does this formula come from?

burgerandcheese

Junior Member
Joined
Jul 2, 2018
Messages
85
pascal's triangle.jpg

This is used to determine the coefficient of the nth row and (r + 1)th column of the Pascal's triangle.
In this book they also used this formula to prove (n, r) = n! /[ r!(n - r)!]
 
Last edited by a moderator:
View attachment 10781

This is used to determine the coefficient of the nth row and (r + 1)th column of the Pascal's triangle.
In this book they also used this formula to prove (n, r) = n! /[ r!(n - r)!]
What book?

I am not sure what your question is. Are you asking why

\(\displaystyle r = 0 \le n \implies \dbinom{n}{r} = 1 \text { and } 0 < r < n \implies \dbinom{n}{r + 1} = \dfrac{n - r}{r + 1} * \dbinom{n}{r}\)

is an equivalent definition to \(\displaystyle \dbinom{n}{r} = \dfrac{n!}{r! * (n - r)!}\)?

Are you asking why the former definition is of use when we have the latter?

Or are you asking something about why the binomial coeffecient is relevant to something?
 
Last edited:
View attachment 10781

This is used to determine the coefficient of the nth row and (r + 1)th column of the Pascal's triangle.
In this book they also used this formula to prove (n, r) = n! /[ r!(n - r)!]

If the book is proving things, I would expect that they would have previously proved whatever they use in any proof! Have you looked to see what justification they give for this?

What book is it? Can you show us exactly what they say in this proof?
 
View attachment 10781

This is used to determine the coefficient of the nth row and (r + 1)th column of the Pascal's triangle.
In this book they also used this formula to prove (n, r) = n! /[ r!(n - r)!]

To answer your question specifically, in order to justify the claim that \(\displaystyle \dbinom{n}{r + 1} = \dfrac{n - r}{r + 1} \dbinom{n}{r}\), we can think about what it means. Suppose we have n items, and already know how many ways there are to choose r of them. How many ways are there to choose r+1? Well, after choosing r, there are n-r other items to choose for the extra one we want, so we can multiply by n-r; but then we could have obtained the same set of r+1 items in r+1 different ways (because any of them might have been the last one we added); so we have to divide by r+1.

There are more natural recurrences I have seen used, but they generally rely on similar (though often simpler) thinking. I expect that something like this is what the book did. But I'll want to see the proof in its entirety (and also what leads up to it) in order to be sure. It depends on their starting point.
 
To answer your question specifically, in order to justify the claim that \(\displaystyle \dbinom{n}{r + 1} = \dfrac{n - r}{r + 1} \dbinom{n}{r}\), we can think about what it means. Suppose we have n items, and already know how many ways there are to choose r of them. How many ways are there to choose r+1? Well, after choosing r, there are n-r other items to choose for the extra one we want, so we can multiply by n-r; but then we could have obtained the same set of r+1 items in r+1 different ways (because any of them might have been the last one we added); so we have to divide by r+1.

There are more natural recurrences I have seen used, but they generally rely on similar (though often simpler) thinking. I expect that something like this is what the book did. But I'll want to see the proof in its entirety (and also what leads up to it) in order to be sure. It depends on their starting point.
@Dr. P

The proof that the recurrence relation and the closed form are equivalent is simple enough by induction, but the OP may not know induction.

I wonder, however, if the OP is asking why we need the recurrence relation when we have the closed form.

If you are computing the sequence

\(\displaystyle \dbinom{n}{0}, \ ... \ \dbinom{n}{n}\) and n is large,

using the recurrence relation and symmetry will greatly reduce the number of computations that need to be done compared to the closed form.

Very badly posed question.
 
I mean, I want to know the proof for the formula, because the book never gave a proof for it.

This was from A-level Pure Mathematics 1 by Hugh Neill and Douglas Quadling:

http://gcecompilation.com/wp-content/uploads/2017/Pure Mathematics -1.pdf

under the topics sequences and binomial theorem. It was first mentioned at page 122 under 8.4 Pascal Sequences

pascal's triangle 2.jpg

Then, it was used again at the bottom of page 135 under the chapter Binomial Theorem and page 136

pascal's triangle 3.PNG
 
To answer your question specifically, in order to justify the claim that \(\displaystyle \dbinom{n}{r + 1} = \dfrac{n - r}{r + 1} \dbinom{n}{r}\), we can think about what it means. Suppose we have n items, and already know how many ways there are to choose r of them. How many ways are there to choose r+1? Well, after choosing r, there are n-r other items to choose for the extra one we want, so we can multiply by n-r; but then we could have obtained the same set of r+1 items in r+1 different ways (because any of them might have been the last one we added); so we have to divide by r+1.

I can't understand still :(
I will need to read this again and again until I understand.
 
I mean, I want to know the proof for the formula, because the book never gave a proof for it.

This was from A-level Pure Mathematics 1 by Hugh Neill and Douglas Quadling:

http://gcecompilation.com/wp-content/uploads/2017/Pure Mathematics -1.pdf

under the topics sequences and binomial theorem. It was first mentioned at page 122 under 8.4 Pascal Sequences

View attachment 10782

Then, it was used again at the bottom of page 135 under the chapter Binomial Theorem and page 136

View attachment 10783

What I see here is that they have defined the "Pascal sequence" by this recursion ("inductive definition")! So no proof of it is needed in your context. I have to say that this is a very strange way to introduce these concepts.

It appears that they have not given any meaning to the sequence or its notation at that point. In particular, they say nothing about the concept of combinations, which I was using as the basis of my explanation.

When they discuss the binomial theorem, they derive the general formula effectively by induction, though not formally. However, they don't seem to justify the claim that Pascal's triangle can be defined equivalently either by this recursion or by adding two numbers from the row above (which I think of as the definition of the triangle).

So it turns out that you don't have to ask your question: The "inductive definition" is just stated as a definition of a sequence, without needing justification. But I think I was right that you were not asking how to do induction, but just where the statement comes from. Now that we have some idea of the context, it is clear that my explanation was for a different context, and you can ignore it.
 
This is not a proof, but gives the ideas used in the proof.

First, the book should really point out that r is from zero through only (n - 1) so the algebraic part of the recursion formula is running from (0 + 1) through {(n - 1) + 1}, meaning from 1 through n.

Second, the recursion algorithm starts with

\(\displaystyle \dbinom{n}{0} = 1,\)

which is exactly the same as you get with the closed form of

\(\displaystyle \dbinom{n}{s} = \dfrac{n!}{s * (n - s)!} \implies \dbinom{n}{0} = \dfrac{n!}{0! * (n - 0)!} = \dfrac{n!}{1 * n!} = 1.\)

Third, using that closed form with r from 0 through n - 1, we get

\(\displaystyle \dbinom{n}{r + 1} = \dfrac{n!}{(r + 1)! * \{n - (r + 1)\}!} = \dfrac{n!}{(r + 1) * r! * \{(n - 1) - r\}} =\)

\(\displaystyle \dfrac{1}{r + 1} * \dfrac{n!}{r!} * \dfrac{1}{\{(n - 1) - r\}!}.\)

Let's analyze that third fraction.

\(\displaystyle (n - r)! = (n - r) * \{(n - r) - 1\}! = (n - r) * \{(n - 1) - r\}! \implies\)

\(\displaystyle \dfrac{1}{\{(n - 1) - r\}!} = \dfrac{n - r}{(n - r)!}.\)

Now substitute back into the expression for the binomial coeffecient.

\(\displaystyle \dbinom{n}{r + 1} = \dfrac{1}{r + 1} * \dfrac{n!}{r!} * \dfrac{n - r}{(n - r)!} = \dfrac{n - r}{r + 1} * \dfrac{n!}{r! * (n - r)!} = \dfrac{n - r}{r + 1} * \dbinom{n}{r}.\)

But that is exactly the algebraic forrmula used in the recursion.

So the closed form and the recursion formula are exactly the same for 0 through n and so are equivalent mathematically.

The recursion approach is, however, more computationally efficient in some circumstances.
 
Last edited:
I forgot to say thank you JeffM and Dr.Peterson for your helpful answers! :) Also, I guess this might affect users because my post will go up and other posts from people who need help may go unnoticed, so sorry! Perhaps I should say thanks in advance next time ~
 
I forgot to say thank you JeffM and Dr.Peterson for your helpful answers! :) Also, I guess this might affect users because my post will go up and other posts from people who need help may go unnoticed, so sorry! Perhaps I should say thanks in advance next time ~
Actually, I feel it is best to wait to give thanks until you feel that you have been fully answered. The primary reason is that those who give answers want, for various reasons, to know that they have been fully responsive. The only way we know that is if the original poster says something along the lines "Got it now. Thanks."

So I, and certainly Dr. P as well, are happy to have been of assistance.
 
Top