Hockey Stick Identity Summation Proof I'm working on a math problem that asks us to prove the following: $$ \text{For all $j,n \in \mathbb{N},$} \sum_{k=0}^n {k \choose j}(n-k) = {{n+1}\choose{j+2}} $$
It is a spinoff of the hockey stick identity: $$ \sum_{k=0}^n {k \choose j} = {{n+1} \choose {j+1}}$$
I am attempting to do this by induction, but have hit a roadblock in my reasoning:
Base Case $\left(j,n =0\right)$
\begin{gather}
        \sum_{k=0}^0 {0\choose 0} (0-0) = {{0+1} \choose {0+2}} \\
        0 = {1 \choose 2} \\
        0 = 0
    \end{gather}
Inductive Case $\left(n \longrightarrow n+1\right)$
\begin{gather}
    \sum_{k=0}^{n+1} {k \choose j}(n-k)\\
    \sum_{k=0}^{n} {k \choose j}(n-k) + {{k+1} \choose {j+1}}({n+1}-{k+1}) \\
    {{n+1}\choose{j+2}} + {{k+1} \choose {j+1}}((n+1)-(k+1)) \\
    {{n+1}\choose{j+2}} + {{k+1} \choose {j+1}}(n-k) \\
    \end{gather}
Is an inductive proof really the best way to go about this, or are there other, better ways? Any help would be appreciated.
 A: I would rewrite the sum as
$$
   \sum_{k=0}^n (n+1) \binom kj - \sum_{k=0}^n (k+1) \binom kj
$$
and replace $(k+1) \binom kj$ by the equivalent $(j+1)\binom{k+1}{j+1}$. This lets you use the ordinary hockey-stick identity to simplify both sums.
A: There is a fairly straightforward combinatorial proof; I’ll point you in the right direction. (In general I find combinatorial proofs more informative and more intuitive than computational proofs.)
First notice that $\binom{n+1}{j+2}$ is the number of ways to choose $j+2$ elements of the set $[n+1]=\{1,2,\ldots,n+1\}$; we’d like to relate that to the sum on the lefthand side.
Suppose that $A$ is a subset of $[n+1]$ with $j+2$ elements. Let $m=\max A$, and let $\ell=\max(A\setminus\{m\})$, so that $\ell$ is the second-largest element of $A$. Let $k=\ell-1$, and let $A_0=A\cap[k]=\{a\in A:a\le k\}$; then $A_0$ is a $j$-element subset of $[k]$, and $m$ is one of the $(n+1)-\ell=n-(\ell-1)=n-k$ elements of $[n+1]$ that are bigger than $\ell$. Can you see how to put these pieces together to show that the sum on the lefthand side also gives the number of ways to choose $j+2$ elements of $[n+1]$.
A: \begin{gather}
    \sum_{k=0}^{n+1} {k \choose j}(n-k)\\
    \sum_{k=0}^{n} {k \choose j}(n-k) + {\color{red}{n+1} \choose {j+1}}({n+1}-{k+1}) \\
    {{n+1}\choose{j+2}} + {\color{red}{n+1} \choose {j+1}}((n+1)-(k+1)) \\
    {{n+1}\choose{j+2}} + {\color{red}{n+1} \choose {j+1}}(n-k) \\
    \end{gather}
