Combinatorial Proof regarding Falling Factorials and sums of Falling Factorials

combinatorial-proofscombinatoricsfactorialsummation

Prove that for every $n$ and $k$ satisfying $1 \le k \le n$,

$$(n)_k = \sum_{i = k}^n k \cdot (i-1)_{k-1}$$

where $(n)_k$ is the falling factorial.

I tried using a combinatorial proof as follows:

Assume we want to pick $k$ distinct balls from a group of $n$ balls. The LHS obviously counts the number of ways we can do this.

The RHS is the sum of ways we can pick $k-1$ balls from smaller sets of balls and incrementally adding to the set until we have our original size of $n$.

There are two things wrong with my interpretation of the right side:

  1. I completely ignore the $k$ in front of $(i-1)$. I am not sure of it's relevance and why it works. I originally thought we are multiplying by the number of ways we can rearrange the balls, but I quickly realized that's taken care of in the $(i-1)_{k-1}$ term.
  2. My interpretation really does not mean anything in the context of the problem. Specifically the $k-1$ and why picking from a smaller group of balls allows us to get to our total number of ways.

I'd appreciate if anyone can provide some intuition in understanding what the right side is telling me and some steps in the right direction.

EDIT:

I was able to rewrite the equation like this:
$$(n)_k = k\sum_{i = k}^n \frac{(i-1)!}{(i-k)!}$$

Best Answer

$ \displaystyle (n)_k = \sum_{i = k}^n k \cdot (i-1)_{k-1}$

$ = k(n-1)_{k-1} + \sum \limits_{i = k}^{n-1} k \cdot (i-1)_{k-1} = k(n-1)_{k-1} + (n-1)_k$

The identity, $ \displaystyle n_k = k(n-1)_{k-1} + (n-1)_k$ can be explained as follows -

Say we have $k$ marked spots in a row on the floor and are now making different arrangements of $k$ balls in those spots taking from $n$ distinct balls that we have. This can be done in $n_k$ ways but we can also keep aside one of the balls $b_1$ and then first count all arrangements with $(n-1)$ balls which is $(n-1)_k$. We then count arrangements with ball $b_1$ that was left aside, place $b_1$ in one of the $k$ spots and then fill rest $(k-1)$ spots taking from $(n-1)$ balls.

Now we could repeat this. Once we keep aside $b_1$ and we are counting ways with $(n-1)$ balls first, we can again have a ball $b_2$ kept aside and count ways with $(n-2)$ balls first.

I hope that explains.

Related Question