The binomial theorem question.

[Aion]

I've been using a method for expanding expressions of the form [imath](x+y)^n[/imath] without explicitly writing out the binomial coefficients. I don't remember exactly where I read it, but it is the following method. The first coefficient is always 1 since,[imath]\binom{n}{0}=1[/imath] to obtain the next coefficient in the expansion we multiply the coefficient of [imath]x[/imath] by the exponent of [imath]x[/imath] and divide by the terms position index.


As an example, consider

[math](x+1)^5=c_1x^5+c_2x^4+c_3x^3+c_4x^2+c_5x+1[/math]
Here the position index is 1 for the first term and then it continues up to 6 terms. Now [imath]c_1=1[/imath], and hence

[math]c_2=\frac{c_1\cdot5}{1}=5[/math][math]c_3=\frac{c_2\cdot4}{2}=\frac{5\cdot4}{2}=10[/math]
Here we don't have to continue since [imath]\binom{n}{k}=\binom{n}{n-k}[/imath]. As you can see this can be applied for [imath](x+y)^n[/imath] as well, and I find it faster than computing the binomial coefficients by hand. I think it's related to Pascal's triangle but I'm not sure how to prove that the algorithm works.

 

[Dr.Peterson]

This is exactly what I do when I need to calculate all the coefficients.

Just observe that [math]\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots2\cdot1}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{1(2)(3)\cdots(k-1)(k)}=1\cdot\frac{n}{1}\cdot\frac{n-1}{2}\cdot\frac{n-2}{3}\cdots\frac{n-k-1}{k}[/math]
For a given k, you just stop when the denominator reaches k.

 

[Aion]

Is this reasoning correct? We know that

[math](x+1)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}[/math]
Now consider the term at the k-th position index. It's equal to
[math]\binom{n}{k-1}x^{n-k+1}=\frac{n(n-1)...(n-k+2)}{k!}x^{n-k+1}[/math]And the k+1 position in the expansion is equal to

[math]\binom{n}{k}x^{n-k}[/math]
But notice that [math]\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}[/math]
Hence to obtain the next coefficient we multiply the previous coefficient by [imath](n-k+1)[/imath], which is the exponent in the previous term and divide by the position index to obtain the next coefficient.

 

[Aion]

Is this reasoning correct? We know that

[math](x+1)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}[/math]
Now consider the term at the k-th position index. It's equal to
[math]\binom{n}{k-1}x^{n-k+1}=\frac{n(n-1)...(n-k+2)}{k!}x^{n-k+1}[/math]And the k+1 position in the expansion is equal to

[math]\binom{n}{k}x^{n-k}[/math]
But notice that [math]\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}[/math]
Hence to obtain the next coefficient we multiply the previous coefficient by [imath](n-k+1)[/imath], which is the exponent in the previous term and divide by the position index to obtain the next coefficient.

I made a typo mistake, I meant that the k-th position index is equal to

[math]\binom{n}{k-1}x^{n-k+1}=\frac{n(n-1)...(n-k+2)}{(k-1)!}x^{n-k+1}[/math]

 

[Dr.Peterson]

Is this reasoning correct? We know that

[math](x+1)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}[/math]
Now consider the term at the k-th position index. It's equal to
[math]\binom{n}{k-1}x^{n-k+1}=\frac{n(n-1)...(n-k+2)}{(k-1)!}x^{n-k+1}[/math] [corrected]
And the k+1 position in the expansion is equal to

[math]\binom{n}{k}x^{n-k}[/math]
But notice that [math]\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}[/math]
Hence to obtain the next coefficient we multiply the previous coefficient by [imath](n-k+1)[/imath], which is the exponent in the previous term and divide by the position index to obtain the next coefficient.

It isn't obvious to me how you "notice" that statement; did you see it by writing out the expression for [imath]\binom{n}{k}[/imath] as you did for [imath]\binom{n}{k-1}[/imath], or some other way?

But another way to show it, in terms of combinatorics, is that if you have found all the [imath]\binom{n}{k}[/imath] sets of [imath]k[/imath] out of [imath]n[/imath] items,, and you want to obtain the ways to choose [imath]k+1[/imath] items, you can choose (for each of them) one of the other [imath]n-k[/imath] items to include; but you will have obtained the same new set from [imath]k+1[/imath] different starting sets (because any of the [imath]k+1[/imath] items in the new set may be the one that was added).

So [math]\binom{n}{k+1}=\binom{n}{k}\cdot\frac{n-k}{k+1}[/math].

 

[Aion]

It isn't obvious to me how you "notice" that statement; did you see it by writing out the expression for [imath]\binom{n}{k}[/imath] as you did for [imath]\binom{n}{k-1}[/imath], or some other way?

I initially assumed the problem was already solved, so I tried multiplying the coefficient by the exponent and dividing by the position index. It was then that I realized the result was equal to [imath]\binom{n}{k}[/imath].

But another way to show it, in terms of combinatorics, is that if you have found all the [imath]\binom{n}{k}[/imath] sets of [imath]k[/imath] out of [imath]n[/imath] items,, and you want to obtain the ways to choose [imath]k+1[/imath] items, you can choose (for each of them) one of the other [imath]n-k[/imath] items to include; but you will have obtained the same new set from [imath]k+1[/imath] different starting sets (because any of the [imath]k+1[/imath] items in the new set may be the one that was added).

So [math]\binom{n}{k+1}=\binom{n}{k}\cdot\frac{n-k}{k+1}[/math].

Apologies Dr. Peterson, I don’t fully understand your proof as I’m not particularly strong in combinatorics.