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.
 A: You need aditivity of binomial coefficients:
$${n\choose s}+{n\choose s+1} = {n+1\choose s+1}$$
so
$$
\underbrace{\binom{s}{s} + \binom{s+1}{s} + \dotsb + \binom{n}{s}}_{n+1\choose s+1} +{n+1\choose s}= \binom{n+1}{s+1} +{n+1\choose s} ={n+2\choose s+1}
$$
A: Recall the classic combinatorial identity
$${n \choose m }={n-1 \choose m-1 }+{n-1 \choose m }.$$
Thus 
\begin{align*}{n+1 \choose s+1 }&={n \choose s }+{n \choose s+1 }\\&={n \choose s }+{n-1 \choose s }+{n-1 \choose s+1 }\\&={n \choose s }+{n-1 \choose s }+{n-2 \choose s }+{n-2 \choose s+1 }\\&\vdots\\&={n \choose s }+{n-1 \choose s }+{n-2 \choose s }+\cdots+{s+1 \choose s+1 }\\&={n \choose s }+{n-1 \choose s }+{n-2 \choose s }+\cdots+{s \choose s }.\end{align*}
A: 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}$$
