# combinatorics – Combinatorial Proof regarding Falling Factorials and sums of Falling Factorials

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}$$

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.