# 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.

• Your base case should be $n=s+1$ (for any $s\geq 0$). The induction step is an increment on $n$. – Graham Kemp Sep 4 '18 at 0:40
• Note that $s$ is fixed. It is $n$ that is changing. The equation has the form $\sum_{k = s}^{n} \binom{k}{s} = \frac{n + 1}{s + 1}$. The RHS counts the number of $(s + 1)$-element subsets of the $(n + 1)$-element set $\{0, 1, 2, \ldots, n\}$. The LHS counts the same thing since the term $\binom{k}{s}$, $s \leq k \leq n$, is the number of $(s + 1)$-element subsets with largest element $k$. – N. F. Taussig Sep 4 '18 at 1:39

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

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

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}