1
$\begingroup$

So I was assigned this homework problem: $$\ {s \choose s} + {s+1 \choose s} +...+ {n \choose s} = {n+1 \choose s+1}$$ for all s and all $n \geq s$ I've tried to email both my professor and my TA and their explanations seem contradictory. My professor responded saying the statement I need to prove is "The formula is correct for $0 \leq s \leq n$." Whereas my TA told me I need to use induction on both variables and I'm not sure how to do that. Any help is appreciated!

1 Answers 1

0

Use induction on $n$. Fix $s \leq n$. If the equation holds then it holds with $n$ cha nged to $n+1$ because of the following identity: $\binom {n+1} {s+1} +\binom {n+1} s=\binom {n+2} {s+1}$. You can verify this identity by writing the binomial coefficients in terms of factorials. To complete the proof you only have to verify the equation with $n$ changed to $n+1$ and $s=n+1$. But this just reduces to $1=1$!