2
$\begingroup$

I am going through a proof for the binomial theorem: $$\begin{align*} (x+y)^n &= (x+y)(x+y)^{n-1}\\ &= (x+y)\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^k\\ &= x\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^k + y\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^k\\ &= \sum_{i=0}^{n-1}\binom{n-1}{k}x^{n-k}y^k + \sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k+1} \end{align*}$$ Let $i=k$ in the first equation and $i=k+1$ in the second equation. Then: $$ (x+y)^n = \sum_{i=0}^{n-1}\binom{n-1}{i}x^{n-i}y^i + \sum_{i=1}^n\binom{n-1}{i-1}x^{n-i}y^i$$


Why can $i$ be both $k$ and $k+1$ in the same formula? Seems like cheating... and a bit confusing later if I want to replace $i$ should I use $k$ or $k+1$?
$$ = x^n + \sum_{i=1}^{n-1}\left(\binom{n-1}{i}+\binom{n-1}{i-1}\right)x^{n-i}y^i + y^n$$ I am not sure where the $x^n$ and $y^n$ come from. Are they taken out of the left summation in order to make $i=0$ become $i=1$? $$\begin{align*} \qquad &= x^n + y^n+\sum_{i=1}^{n-1}\binom{n}{i}x^{n-i}y^i\\ &= \sum_{i=0}^n \binom{n}{i}x^{n-i}y^i. \end{align*}$$

1 Answers 1

7

The $k$ in the summation is a so-called "dummy-variable". It is not really "part" of the formula, in that we can change the name without changing the meaning. So for example, $$\sum_{i=0}^{n-1}\binom{n-1}{i}x^{n-i}y^i = \sum_{j=0}^{n-1}\binom{n-1}{j}x^{n-j}y^j.$$ You are not really setting $i=k$; rather, what you are doing is you are changing the name of the index in the first summation; and in the second summation, you are "re-indexing". For example, to add $$a_1+a_2+a_3+\cdots +a_{10}$$ we can write $$\sum_{i=1}^{10}a_i,$$ but we can also write $$\sum_{j=0}^{9}a_{j+1}$$ or $$\sum_{k=2}^{11}a_{k-1}.$$ This is known as "re-indexing". This is what we are doing in the second summation, reindexing so that the index runs from $1$ to $n$.

If it makes you nervous, you can change the name of the index in the first sum to $i$, and re-index and change the name to $j$ in the second sum as a first step: $$\sum_{i=0}^{n-1}\binom{n-1}{i}x^{n-i}y^i + \sum_{j=1}^n\binom{n-1}{j-1}x^{n-j}y^j$$ and then change the $j$ in the second sum to an $i$; again, because this is a "dummy variable", it's not really playing any role in the equation except that of a record-keeper.

That's so that we can rewrite the sum of sums as a single summation later on.

As to the $x^n$ and the $y^n$, going back to my example above, note that $$\sum_{i=1}^{10}a_i = a_1+a_2+a_3+\cdots+a_9+a_{10}.$$ But we can also write it as: $$a_1 + (a_2+\cdots+a_9+a_{10}) = a_1 + \sum_{i=2}^{10}a_i$$ or as $$(a_1+\cdots+a_9) + a_{10} = \sum_{i=1}^9a_i + a_{10}.$$ This is what is being done: we separate out the first summand (that corresponds to the $i=0$ case) in the first sum, and we separate out the last summand (corresponding to $i=n$) in the second sum. Again, this is so that both sums run over the exact same index set ($1$ through $n-1$), so that we can write it as a single summation.

  • 0
    Thanks for the fix, totally missed the + sign. Just added it, in case someone else finds this answer.2012-02-11