1
$\begingroup$

So, I would like to prove the following: $$\forall n,k\in\mathbb{N}_0, n\geq k+1: \sum_{i=0}^{k}{{n-i-1}\choose {k-i}}={n\choose k}$$ First of, i exploited trivial symmetry of the binomial coefficients to obtain: $$\sum_{i=0}^{k}{{n-i-1}\choose {k-i}}=\sum_{i=0}^{k}{{n-i-1}\choose {n-k-1}}$$ Now I proceeded by induction on $n$. The base step: ($n=k+1$): $$\sum_{i=0}^k{{k-i}\choose 0}=k+1={{k+1}\choose 1}={{k+1}\choose k}$$ But now here in the inductive step, I'm quite unsure how to proceed $$\sum_{i=0}^k{{n-i-1}\choose {n-k-1}}={n\choose k}$$ (the premise) and this should follow: $$\sum_{i=0}^k{{n-i}\choose{n-k}}={{n+1}\choose k}$$ All i managed to do was to "simplify" by symmetry: $$\sum_{i=0}^k{{n-i}\choose{n-k}}=\sum_{i=0}^k{{n-i}\choose{k-i}}$$ But from here i have no idea, would you please suggest further steps and how should i proceed from here?

$\endgroup$

marked as duplicate by Holo, Isaac Browne, Key Flex, N. F. Taussig combinatorics Oct 5 '18 at 8:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.