<s>[INST] Induction step in proof that $\binom{s}{s} + \binom{s + 1}{s} + \cdots + \binom{n}{s} = \binom{n + 1}{s + 1}$ Prove by induction that (binomial theorem)
$$
\binom{s}{s} + \binom{s+1}{s} + \dotsb + \binom{n}{s} = \binom{n+1}{s+1}
$$
for all $s$ and all $n>s$.
I used base case $s=0$, and I got my base case to work. However when I go to my induction step, I can’t seem to get it to work.
 [/INST] Alternatively, note that:
$${n\choose m}={n\choose n-m}; \ \text{so}:\\
\begin{align}&\binom{s}{s} + \binom{s+1}{s} + \binom{s+2}{s} +\binom{s+3}{s} +\dotsb + \ \ \ \binom{n}{s} \ \ \ \ = \binom{n+1}{s+1} \iff \\
&\color{red}{\binom{s}{0} + \binom{s+1}{1}} + \color{blue}{\binom{s+2}{2}} +\color{green}{\binom{s+3}{3}} +\dotsb + \mathbf{\color{purple}{\binom{n}{n-s}}} = \binom{n+1}{n-s}.\end{align}$$
Now we get:
$$\begin{align}\color{red}{\binom{s}{0} + \binom{s+1}{1}}&=\binom{s+2}{1};\\
\binom{s+2}{1} + \color{blue}{\binom{s+2}{2}}&=\binom{s+3}{2};\\
\binom{s+3}{2} + \color{green}{\binom{s+3}{3}}&=\binom{s+4}{3};\\
\vdots\\
\binom{n}{n-s-1} + \mathbf{\color{purple}{\binom{n}{n-s}}}&=\binom{n+1}{n-s} \ \ \ \ \ \ \ \ \ (\text{inductive hypothesis});\\
\binom{n+1}{n-s} + \binom{n+1}{n-s+1}&=\binom{n+2}{n-s+1} \ \ (\text{inductive step}).\end{align}$$
</s>