Prove the equation:
$$\sum_{k=1}^n{{k}\choose{j}}k = {{n+1}\choose{j+1}}n - {{n+1}\choose{j+2}}$$
My solution:
We have $n+1$ players numbered from $1$ to $n+1$. We want to play a team game that requires:
- $j$ players in team $A$,
- $n-j$ players in team $B$,
- $1$ special player, who is a player on one of the teams,
- $1$ referee and that the players on team $A$ and the special player have lower numbers than the referee.
On the LHS:
- We choose the player numbered $k+1$ as referee.
- From the players numbered $1$ to $k$ (there are $k$ of them) we select $j$ players for team $A$, the remaining $n-j$ players will go to team $B$.
- From the players numbered $1$ to $k$ (there are $k$ of them) we select a special player.
Choosing the player numbered $k+1$ as referee ensures that we do not count the same hand twice (because $k$ is increasing and the player numbered $k+1$ could not have been chosen as referee in any previous hand).
On the RHS:
- From the players numbered $1$ to $n+1$ (there are $n+1$ of them), we select $j+1$. These are the players for team $A$ and the referee - the player with the highest number among those selected becomes the referee. This ensures that the players for team $A$ will never have a higher number than the referee.
- We then select a special player from among the $n$ players numbered $1$ to $n$ (the special player will never be the player numbered $n+1$, because he must have a lower number than the referee, and then this would be impossible). On the other hand, we are not sure at this stage that the special player will have a lower number than the referee (if the special player belongs to team $B$, this is not guaranteed), so we have to subtract those hands in which this happens.
- We subtract the hands in which $j+2$ players are selected. The player with the highest number is the special player. The player with a number $1$ less than the highest number is the referee.
Is that correct?