1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your base case should be $n=s+1$ (for any $s\geq 0$). The induction step is an increment on $n$. $\endgroup$ – Graham Kemp Sep 4 '18 at 0:40
  • $\begingroup$ 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$. $\endgroup$ – N. F. Taussig Sep 4 '18 at 1:39
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.