La induccion sobre n, para el caso de 1 es trivial. Lo que tienes que buscar es la relacion con n y n+1 para la induccion...Para eso mira que, por el teorema de pPascal,
\( \displaystyle\binom{n+1}{k+1}=\displaystyle\binom{n}{k}+\displaystyle\binom{n}{k+1} \)
puedes suponer k<n y para el caso donde n=k pues lo puedes desarrollar facilmente.