Sum of Binomial Expansion | Spivak Chapter 2, Excercise 3 part d

[sleepingMantis]

Hello,

I am working through Spivak for self study and sharpening my math skills. I have become stuck on an exercise.

What I need to show is the following:

$$
(a + b) \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j} = \sum_{j = 0}^{n + 1} \binom{n+1}{j} a^{n-j + 1}b^{j}
$$

My attempt, starting from the LHS. Expanding the brackets:

$$
(a + b) \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j} = a \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j} + b \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j}
\\ = \sum_{j = 0}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{j = 0}^{n} \binom nj a^{n-j}b^{j+1}
$$

Now I know a useful equality (that I proved earlier) is:

$$
\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}
$$

However I am not sure how to proceed. Any tips would be much appreciated!

 

[fresh_42]

The trick is to shift the summation, i.e. replace $j$ by $i+1$ or $i-1$. I find it easiest to separate the terms for $j=0$ and $j=n$ and then get rid of $j \pm 1$ in the exponent by the substitutions I mentioned. (I would have to do it on my own to see which sum is transformed by which substitution, but you should be able to figure it out.)

 

[mathman]

Set j'=j+1 for the second summation.

 

[sleepingMantis]

Thank you guys, plugging in k = j+1

$$
= \sum_{j = 0}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k}
$$

This looks to be on the right track, but does it matter that the binomial brackets in the two summations have different variables, namely $j$ and $k$ ?

 

[fresh_42]

Thank you guys, plugging in k = j+1

$$
= \sum_{j = 0}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k}
$$

This looks to be on the right track, but does it matter that the binomial brackets in the two summations have different variables, namely $j$ and $k$ ?

No, these are just names. You could as well sum up $\sum_{tree=0}^n \binom{n}{tree} ...$ but this would last too long to write. But you will have to look for the boundaries if you write the sums again under one summation. $\sum_{j=0}^n a_j + \sum_{k=1}^n b_k = a_0 + \sum_{tree=1}^n (a_{tree}+b_{tree})$.

 

[sleepingMantis]

Thanks, so to write the sum under one summation, the limits have to be consistent.

But now I am confused. If I plug in k into the first sum, I will end up with:

$$
= \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-(k-1)}b^{k-1} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k}
$$

But this seems to take me away from where I need to be.

Am I on the right track here?

 

[fresh_42]

Let's step back a bit to your post number 4. You wrote

$$
= \sum_{j = 0}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k}
$$

by doing the substitution @mathman suggested: $k=j+1$ from the second sum. But if $j$ ran from $0$ to $n$ then $k$ runs from $1$ to $n+1$.

Let's assume you corrected this. Then we have one term at the beginning of the first sum and one at the end of the second sum which have no counterparts. Hence your sum reads
$$
= \binom n0 a^{n+1-0}b^0 + \sum_{j = 1}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k} + \binom {n}{n}a^{n+1-(n+1)}b^k
$$
Now you can rename the indices again and substitute $k$ by $j$ which allows you to write the summation in one sum from $1$ to $n$ plus the two lonely terms. The crucial part is, and that's why you made this, that the powers of $a$ and $b$ match, i.e. we can add the coefficients now: $\binom nj + \binom {n}{j-1}$.

 

[sleepingMantis]

Let's step back a bit to your post number 4. You wrote

by doing the substitution @mathman suggested: $k=j+1$ from the second sum. But if $j$ ran from $0$ to $n$ then $k$ runs from $1$ to $n+1$.

Let's assume you corrected this. Then we have one term at the beginning of the first sum and one at the end of the second sum which have no counterparts. Hence your sum reads
$$
= \binom n0 a^{n+1-0}b^0 + \sum_{j = 1}^{n} \binom nj a^{n+1-j}b^{j} + \sum_{k = 1}^{n} \binom {n}{k-1} a^{n+1-k}b^{k} + \binom {n}{n}a^{n+1-(n+1)}b^k
$$
Now you can rename the indices again and substitute $k$ by $j$ which allows you to write the summation in one sum from $1$ to $n$ plus the two lonely terms. The crucial part is, and that's why you made this, that the powers of $a$ and $b$ match, i.e. we can add the coefficients now: $\binom nj + \binom {n}{j-1}$.

Wow that is an excellent explanation. Thank you very much I see now. I will crank out a few more of these problems but I can see how to use this trick.

 

[WWGD]

This seems like a step in induction used to prove the general formula for the binomial coefficient for $(a+b)^n$ The formula for exponent n+1 is clearly that for n multiplied by (a+b).

 

[WWGD]

Or you can give a combinatorial argument on expanding the expression :
(a+b)(a+b)...(a+b) n times. Each monomial will have n terms, k a's and n-k b's. In how many ways can you make the choice?

 

[sleepingMantis]

This seems like a step in induction used to prove the general formula for the binomial coefficient for $(a+b)^n$ The formula for exponent n+1 is clearly that for n multiplied by (a+b).

Thank you yes that is correct - this is a step in the induction proof

 

[sleepingMantis]

Or you can give a combinatorial argument on expanding the expression :
(a+b)(a+b)...(a+b) n times. Each monomial will have n terms, k a's and n-k b's. In how many ways can you make the choice?

Would that be the choice for the coefficient of each term in the expression?

 

[fresh_42]

Would that be the choice for the coefficient of each term in the expression?

... each term in the expression for $(a+b)^n$, yes.

We have $n$ numbered balls and draw $k$ of them without return and disrespect of the order. Those $k$ balls are labeled as $a$, the rest as $b\, : \, n=k+(n-k) \longrightarrow a^{k}b^{n-k}$. Then $\binom nk$ is the number of possibilities to get the same result, since we do not consider the numbers on the balls: $\{\,1,\ldots ,n\,\} = \{\,n_1,\ldots,n_k\,\}_a\, \dot \cup \,\{\,n_{k+1},\ldots ,n_n\,\}_b$ and there are $\binom nk$ many possible sets $\{\,n_1,\ldots,n_k\,\}$.

 

[WWGD]

Would that be the choice for the coefficient of each term in the expression?

Correct. For the coefficient of $a^kb^{n-k}$ There are C(n,k) ways of choosing the k a's from the product.

 

[sleepingMantis]

... each term in the expression for $(a+b)^n$, yes.

We have $n$ numbered balls and draw $k$ of them without return and disrespect of the order. Those $k$ balls are labeled as $a$, the rest as $b\, : \, n=k+(n-k) \longrightarrow a^{k}b^{n-k}$. Then $\binom nk$ is the number of possibilities to get the same result, since we do not consider the numbers on the balls: $\{\,1,\ldots ,n\,\} = \{\,n_1,\ldots,n_k\,\}_a\, \dot \cup \,\{\,n_{k+1},\ldots ,n_n\,\}_b$ and there are $\binom nk$ many possible sets $\{\,n_1,\ldots,n_k\,\}$.

Correct. For the coefficient of $a^kb^{n-k}$ There are C(n,k) ways of choosing the k a's from the product.

Thank you, so the argument is (just to make sure I have it):

We have the product $(a + b)^n$. From this product we generate monomials of the form $C_{n, k} a^kb^{n-k}$, where $k \leq n$. Each of the $a$'s can be selected in $\binom{n}{k}$ ways. By symmetry, each of $b$'s can be picked in $\binom{n}{n-k}$ ways. Hence $C_{n, k} = \binom{n}{k}$.

Therefore $(a + b)^n$ is the sum of $\binom{n}{k} a^kb^{n-k}$.

 

[fresh_42]

Thank you, so the argument is (just to make sure I have it):

You have it.

Since $a\cdot \ldots \cdot a$ is commutative, we do not have to respect the order.
Since the $a$'s cannot be distinguished, we do not have to respect the numbers on the balls.
Since once a ball is drawn, i.e. an $a$ selected, we have only $n-1$ positions left to fill in $a\cdot \ldots \cdot a \cdot b \cdot \ldots \cdot b$, hence we do not return the ball.

 

[WWGD]

Thank you, so the argument is (just to make sure I have it):

We have the product $(a + b)^n$. From this product we generate monomials of the form $C_{n, k} a^kb^{n-k}$, where $k \leq n$. Each of the $a$'s can be selected in $\binom{n}{k}$ ways. By symmetry, each of $b$'s can be picked in $\binom{n}{n-k}$ ways. Hence $C_{n, k} = \binom{n}{k}$.

Therefore $(a + b)^n$ is the sum of $\binom{n}{k} a^kb^{n-k}$.

Correct. And like Fresh mentioned this is true in commutative rings.

 

[sleepingMantis]

@fresh_42 , @WWGD

Thank you both for your help and ideas, I am learning a lot of cool math and problem solving techniques on this forum!