<s>[INST] Proof of the binomial theorem by induction clarification This is an exercise from Spivak's "Calculus".

3.d. Prove the "binomial theorem": If $a$ and $b$ are any numbers and $n$ is a natural number, then
\begin{align} (a+b)^n &= a^n + {n \choose 1}a^{n-1}b + {n \choose 2}a^{n-2}b^2 + \dots + {n \choose n-1}ab^{n-1} + b^n \\ &= \sum_{j=0}^n {n \choose j} a ^{n-j}b^j \end{align}

The solution is given as

The binomial theorem is clear for $n=1$. Suppose that
$$(a+b)^n=\sum_{j=0}^n{n\choose j}a^{n-j}b^j$$
Then
\begin{align}
(a+b)^{n+1}&=(a+b)(a+b)^n=(a+b)\sum_{j=0}^n{n\choose j}a^{n-j}b^j\\
&=\sum_{j=0}^n{n\choose j}a^{n+1-j}b^j+\sum_{j=0}^n{n\choose j}a^{n-j}b^{j+1}\\
&=\sum_{j=0}^n{n\choose j}a^{n+1-j}b^j+\sum_{j=1}^{n+1}{n\choose j-1}a^{n+1-j}b^j\ \text{(replacing }j \text{ by } j-1 \text)\\
&=\sum_{j=0}^{n+1}{n+1\choose j}a^{n+1-j}b^j
\end{align}

My question is similar to the one asked here, but it is not about the change of indices. What were the steps to combine the two summations at the end?
 [/INST] It is Pascal's rule:
$${n\choose j}+{n\choose j-1}={n+1\choose j}$$
So we have
\begin{align}
(a+b)^{n+1}&=(a+b)(a+b)^n\nonumber \\
&=(a+b)\sum_{j=0}^{n}{n\choose j}a^{n-j}b^j\nonumber \\
&=\sum_{j=0}^{n}{n\choose j}a^{n-j+1}b^j +\sum_{j=0}^{n}{n\choose j}a^{n-j}b^{j+1}\nonumber \\
&={n\choose 0}a^{n+1}+\sum_{j=1}^n{n\choose j}a^{n-j+1}b^j+\sum_{j=1}^{n+1}{n\choose j-1}a^{n-j+1}b^j\nonumber \\
&={n\choose 0}a^{n+1}+{n\choose n}b^{n+1}+\sum_{j=1}^{n}\left[{n\choose j}+{n\choose j-1}\right]a^{n-j+1}b^j\nonumber \\
&={n+1\choose 0}a^{n+1}+{n+1\choose n+1}b^{n+1}+\sum_{j=1}^n{n+1\choose j}a^{n-j+1}b^j\nonumber \\
&=\sum_{j=0}^{n+1}{n+1\choose j}a^{n+1-j}b^j\nonumber
\end{align}
</s>