# Binomial Theorem Inductive Proof - a reindexing moment

I'm copying a proof from someone else and they make this move I don't feel comfortable with. So in the inductive step we assume $${ \left( x+y \right) }^{ n }= \sum _{ m=0 }^{ n }{ \left( \begin{matrix} n \\ m \end{matrix} \right) } { x }^{ m }{ y }^{ n-m }$$, multiply both sides by $${ \left( x+y \right) }$$, distribute the sum and pull in the $$x$$ and $$y$$ to get

$${ { \left( x+y \right) }^{ n+1 } }\quad =\quad \sum _{ m=0 }^{ n }{ \left( \begin{matrix} n \\ m \end{matrix} \right) } { x }^{ m+1 }{ y }^{ n-m }\quad +\quad \sum _{ m=0 }^{ n }{ \left( \begin{matrix} n \\ m \end{matrix} \right) } { x }^{ m }{ y }^{ n+1-m }$$

Then we let $$s=m+1$$ and use this to reindex the first sum:

$${ { \left( x+y \right) }^{ n+1 } }\quad =\quad \sum _{ s=1 }^{ n }{ \left( \begin{matrix} n \\ s-1 \end{matrix} \right) } { x }^{ s }{ y }^{ n+1-s }\quad +\quad \sum _{ m=0 }^{ n }{ \left( \begin{matrix} n \\ m \end{matrix} \right) } { x }^{ m }{ y }^{ n+1-m }$$

This proof says we can now just let $$s=m$$, which sets us up to use Pascal's Identity, but I find this strange to do, since we just had $$m=s-1$$ in the previous line. Is this okay or is there another way to go about this?

• I suppose that, when you wrote $\binom n{s-1}$, what you meant was $\binom n{m-1}$. – José Carlos Santos May 20 at 17:03

The main thing in the proof is that: $$\sum_{m=0}^n\binom{n}{m}x^{m+1}y^{n-m}=\sum_{m=1}^{n+1}\binom{n}{m-1}x^{m}y^{n+1-m}\tag1$$

This can also be observed without interference of any $$s$$.

If you agree that $$(1)$$ is correct then just go on ignoring the artificial $$s$$ and apply the equality $$\binom{n}{m-1}+\binom{n}{m}=\binom{n+1}{m}$$

This leads to:$$(x+y)^{n+1}=\cdots=\sum_{m=0}^{n+1}\binom{n+1}{m}x^my^{n+1-m}$$q.e.d.

This is OK because you're setting $$m=s$$ only in the second sum, which is a trivial change of variable since the index is free, or a dummy. Thus, in the first sum, we still have $$s=m+1.$$

Another way to see this is to make the transformation $$m\mapsto m-1$$ in the first sum. This gives the $$\sum_{m=1}^{n+1}{\binom{n} {m-1} {x}^{m} y^{n+1-m}},$$ where the upper limit is now $$n+1,$$ not $$n$$ as you write.

I would do it like this:

$$\begin{array}\\ ( x+y )^{ n+1 } &= \sum _{ m=0 }^{ n }\binom{ n}{ m} x^{ m+1 } y^{ n-m } +\sum _{ m=0 }^{ n }\binom{ n}{ m} x^{ m } y^{ n+1-m }\\ &= \sum _{ m=1 }^{ n+1 }\binom{ n}{ m-1} x^{ m } y^{ n-(m-1) } +\sum _{ m=0 }^{ n }\binom{ n}{ m} x^{ m } y^{ n+1-m }\\ &= \sum _{ m=1 }^{ n }\binom{ n}{ m-1} x^{ m } y^{ n-m+1 }+x^{ n+1 } +\sum _{ m=1 }^{ n }\binom{ n}{ m} x^{ m } y^{ n+1-m }+y^{n+1}\\ &= \sum _{ m=1 }^{ n }\left(\binom{ n}{ m-1}+\binom{ n}{ m} \right) x^{ m } y^{ n-m+1 }+x^{ n+1 } +y^{n+1}\\ &= \sum _{ m=1 }^{ n }\binom{ n+1}{ m} x^{ m } y^{ n-m+1 }+x^{ n+1 } +y^{n+1}\\ &= \sum _{ m=0 }^{ n+1 }\binom{ n+1}{ m} x^{ m } y^{ n-m+1 }\\ \end{array}$$

My general principle when two (or more) sums overlap is to separate the parts which overlap from the parts that don't, and then combine them.