Binominial theorem proof without induction

AI Thread Summary
The discussion centers on proving the binomial theorem without induction. While one participant suggests using Taylor's expansion, they acknowledge that induction is still necessary for a complete proof. A combinatorial proof is presented, explaining that the coefficient of x^k y^(n-k) in the expansion of (x + y)^n corresponds to the number of ways to choose k x's from n factors, represented by C(n, k). Participants explore the relationship between combinations and permutations, noting that proving these requires induction, particularly when discussing the generalized product rule. Ultimately, the conversation highlights the challenges of proving the binomial theorem without relying on induction.
Werg22
Messages
1,431
Reaction score
1
I was wondering, is there any way to prove the bominial theorem without the use of induction? Thanks.
 
Mathematics news on Phys.org
My official answer: kinda.

If you use Taylor's expansion theorem on (x+a)^m, you'll find that f^{(n)}(0)/n! vanishes for n greater than m. But to prove that, you'll need induction even though it is super evident.
 
sum(C(n,k)*x^k * y^(n-k), k = 0, 1, ..., n) = (x + y)^n

You can give a combinatorial proof.

Pf.
Consider the n factors of the expansion
(x + y)^n = (x+y)(x+y) * * * (x + y)

Now in this expansion, the coefficient of x^ky^(n-k) is the number of different ways we can select k x's from the n available factors. The total number of such selections of size k from a collection of size n is C(n, k), and we're done.
 
i will guess not, unless the versiom of the statement being proved is so weak as not to have any explicit content.
 
ircdan said:
sum(C(n,k)*x^k * y^(n-k), k = 0, 1, ..., n) = (x + y)^n
Pascal's triangle. The proof that this is true for all n requires induction. :frown:
 
ircdan said:
sum(C(n,k)*x^k * y^(n-k), k = 0, 1, ..., n) = (x + y)^n

You can give a combinatorial proof.

Pf.
Consider the n factors of the expansion
(x + y)^n = (x+y)(x+y) * * * (x + y)

Now in this expansion, the coefficient of x^ky^(n-k) is the number of different ways we can select k x's from the n available factors. The total number of such selections of size k from a collection of size n is C(n, k), and we're done.

Could you please explain "Now in this expansion, the coefficient of x^ky^(n-k) is the number of different ways we can select k x's from the n available factors."? How do you come to this conclusion without knowledge of the binominial theorem?
 
Werg22 said:
Could you please explain "Now in this expansion, the coefficient of x^ky^(n-k) is the number of different ways we can select k x's from the n available factors."? How do you come to this conclusion without knowledge of the binominial theorem?
Ok apparently my proof was way too vague. Here is an example to help explain what's going on. For notation below, when i say xx i mean x*x = x^2, so I'm multiplying.

Ok here is an example. Consider the expansion

(x + y)^3 = (x + y)(x + y)(x + y)
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy (1)

and collecting like terms this is x^3 + 3x^2y + 3xy^2 + y^3, call this (2).

Ok now the products in the expansion of (x + y)^3 are formed by forming all products of a term in the first factor, x or y, times a term in the second factor and times a term in the third factor. There are two choices for each term, so there are 2^3 = 8 such products.

Ok, now how many products in (1) contain k x's and 3 - k y's? This is the same as asking for the coefficient of x^(3 -k)y^k in (2). Note we formed all possible products of x's and y's, and note these are just three letter sequences of x's and y's, so we are really asking for the number of 3 letter sequences with k x's and 3-k y's, which is just C(3,k). (Note you only have to choose k x's, asking for 3-k y's isn't needed, but i mentioned it to help clarify)

For the binomial theorem,
sum(C(n,k)*x^k * y^(n-k), k = 0, 1, ..., n) = (x + y)^n

we do the same thing, except our product is

(x + y)^n = (x + y)(x + y) *** (x + y) "n times"

We have n factors in this expansion. Using the same argument as above we get C(n, k) as the coefficient of the x^(n-k)y^k term.



Another way to do it. Consider (x + y)^n = (x + y)(x + y)***(x + y). Now think of each factor as a position in a bitstring of length n, put a 1 in the position if you choose an x from that factor, put a 0 if you choose a y. Then the coefficient of x^ky^(n-k) = the number of bitstrings of length n with k 1's = C(n, k) once again.
 
quasar987 said:
Pascal's triangle. The proof that this is true for all n requires induction. :frown:
Ohhhhh I think I see what you mean.

To prove C(n,k) is the number of r-combinations of a set of n elements you need to use the fact that P(n,r) is the number of r-permutations of a set with n elements.

To prove P(n,r) is the number of r-permutations of a set with n elements you need to use the generalized product rule.

But the catch is, to prove the generalized form of the product rule, you need to use induction:frown: So even though I technically didn't use induction, it seems C(n,k) relies on a result that must be proved by induction. Unless there is another way to prove the product rule without induction? I don't know if there is, if so, then everything works without any use of induction right?
 
Last edited:
ircdan said:
Ohhhhh I think I see what you mean.

To prove C(n,k) is the number of r-combinations of a set of n elements you need to use the fact that P(n,r) is the number of r-permutations of a set with n elements.

To prove P(n,r) is the number of r-permutations of a set with n elements you need to use the generalized product rule.

But the catch is, to prove the generalized form of the product rule, you need to use induction:frown: So even though I technically didn't use induction, it seems C(n,k) relies on a result that must be proved by induction. Unless there is another way to prove the product rule without induction? I don't know if there is, if so, then everything my proof works and it works without any use of induction right?

PS: I haven't read your in depth explanation yet, I'm on to it.

Well if what you are saying is how to prove C(n,k) is n!/k!(n-k)!, this is simple probabilty. Say you have a selection n different numbers to form a k digits number. For the first the digit you have a choice of n number, the second digit a choice of n-1 and so on. This leads to the conclusion that there is n(n-1)...(n-k+1) possibilities. However, since some of these possibilites have the same numbers but with different positions. We consider a group of possibilities with number of this type. In that group, we have k digits and k numbers to chose from. Hence, this group countains exactly k! numbers. We now know that exactly n(n-1)...(n-k+1) /k! combinations are possible, taking account of reoccurance of the same digits. n(n-1)...(n-k+1)/k! can be written n!/k!(n-k)!.
 
  • #10
Werg22 said:
For the first the digit you have a choice of n number, the second digit a choice of n-1 and so on. This leads to the conclusion that there is n(n-1)...(n-k+1) possibilities.
You need to use induction to prove that result, it's called the product rule. We use it all the time, but the proof is by induction(at least the one I've seen). I don't know if there is another way to prove it. I think that's why quasar987 was saying, I'm not sure though hehe:smile:
 
  • #11
By the way, thanks for your explanation, that is an elegant proof.
 
  • #12
Werg22 said:
By the way, thanks for your explanation, that is an elegant proof.
You bet:smile:

PS: And I'm still really new to combinatorics, so hopefully no horrible errors in that proof hehe.
 
  • #13
One of our assignements in discrete scructures was to find a 'combinatorial' (or 'counting') proof to this very problem. The solution already given is the one I found.
 

Similar threads

Back
Top