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*}$$


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.

  • $\begingroup$ Thanks for the fix, totally missed the + sign. Just added it, in case someone else finds this answer. $\endgroup$ – Travis Feb 11 '12 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.