The binomial theorem question.

[Aion]

I've been using a method for expanding expressions of the form $(x+y)^n$ 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,$\binom{n}{0}=1$ to obtain the next coefficient in the expansion we multiply the coefficient of $x$ by the exponent of $x$ and divide by the terms position index.


As an example, consider

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

$$c_2=\frac{c_1\cdot5}{1}=5$$$$c_3=\frac{c_2\cdot4}{2}=\frac{5\cdot4}{2}=10$$
Here we don't have to continue since $\binom{n}{k}=\binom{n}{n-k}$. As you can see this can be applied for $(x+y)^n$ 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 $$\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}$$
For a given k, you just stop when the denominator reaches k.

 

[Aion]

Is this reasoning correct? We know that

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

$$\binom{n}{k}x^{n-k}$$
But notice that $$\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}$$
Hence to obtain the next coefficient we multiply the previous coefficient by $(n-k+1)$, 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

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

$$\binom{n}{k}x^{n-k}$$
But notice that $$\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}$$
Hence to obtain the next coefficient we multiply the previous coefficient by $(n-k+1)$, 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

$$\binom{n}{k-1}x^{n-k+1}=\frac{n(n-1)...(n-k+2)}{(k-1)!}x^{n-k+1}$$

 

[Dr.Peterson]

Is this reasoning correct? We know that

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

$$\binom{n}{k}x^{n-k}$$
But notice that $$\binom{n}{k-1}\frac{(n-k+1)}{k}=\binom{n}{k}$$
Hence to obtain the next coefficient we multiply the previous coefficient by $(n-k+1)$, 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 $\binom{n}{k}$ as you did for $\binom{n}{k-1}$, or some other way?

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

So $$\binom{n}{k+1}=\binom{n}{k}\cdot\frac{n-k}{k+1}$$.

 

[Aion]

It isn't obvious to me how you "notice" that statement; did you see it by writing out the expression for $\binom{n}{k}$ as you did for $\binom{n}{k-1}$, 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 $\binom{n}{k}$.

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

So $$\binom{n}{k+1}=\binom{n}{k}\cdot\frac{n-k}{k+1}$$.

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