Induction step in proof that $\binom{s}{s} + \binom{s + 1}{s} + \cdots + \binom{n}{s} = \binom{n + 1}{s + 1}$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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