Proof by Induction: Series of binomial coefficients with same k-length subsets

Question

I have no idea how to prove this binomial equation identity. For reference this is included in Discrete Mathematics for Computer Scientists by Clifford Stein, Robert Drysdale and Kenneth Boggart, problem 4.1.6.

I understand how to do induction proof, however this particular one eludes me for no reason. Can anyone help me? I'd very much appreciate the help.

Answer 1

Write it as $$ \text{stuff} + \dotsb + \binom nk = \binom{n+1}{k+1} $$ Do you know any identity involving $\binom nk$ and $\binom{n+1}{k+1}$?

Answer 2

A slightly different version of Steven’s hint: what happens if you add $\dbinom{n+1}k$ to both sides of

$$\sum_{j=k}^n\binom{j}k=\binom{n+1}{k+1}\;?$$

Can you simplify anything?

Answer 3

Hint: Consider the geometric series

$(1+x)^k + (1+x)^{k+1}+ (1+x)^{k+2}+...+(1+x)^n$