Algebraic proof regarding falling factorials

Question

Let $n$ and $k$ be positive integers with $n \ge k$. Give an algebraic proof that $$(n)_k = (n-1)_k + k\cdot(n-1)_{k-1},$$ where $(n)_k$ is a falling factorial: $(n)_k$ = $(n)(n-1)(n-2)\ldots(n-k+1)$.

I started by turning LHS into

$$\frac{n!}{(n-k)!} = \frac{((n+k)-k)!}{(n-k)!}$$

I tried doing this after:

$$ = \frac{(((n+k)-k)(n-1))!}{(n-k)!}$$

but I really have no idea where else to proceed. I'm not sure how I can split it up or move past this. Does anyone think they can point me in the right path?

Answer 1

General hint:

When proving $a=b$, it is not always the easiest to start with $a$ and convert it into $b$. There are several other options that can be easier to do, including, but not limited to:

• Proving that $a-b=0$
• Proving that $|a-b|=0$
• Proving that $(a-b)^2=0$
• Proving that $a=c$ and that $b=c$.
• Proving that $a\leq b$ and $b\leq a$

---

You seem to be stuck because you only tried the head-on way of taking $a$ and converting it into $b$. Now, this is possible*, but it is by no means the easiest way. In fact, the easiest way in this case would be to modify both sides of the equation, and show they both equal some other expression.

In particular, the same way you converted the LHS, you can also convert the RHS into

$$\frac{(n-1)!}{(n-1-k)!} + k\cdot\frac{(n-1)!}{(n-1-(k-1))!} $$

Now, use the fact that $(n-1-(k-1))! = (n-k)! = (n-k)\cdot (n-1-k)!$

and sum up the two fractions.

---

* It is possible, because:

$$\begin{align} (n)_k &= \frac{n!}{(n-k)!}\\ &= \frac{n! - k\cdot(n-1)! + k\cdot (n-1)! }{(n-k)!}\\ &=\frac{[n\cdot(n-1)! - k\cdot(n-1)!] + k\cdot(n-1)!}{(n-k)!}\\ &=\frac{n\cdot(n-1)! - k\cdot(n-1)!}{(n-k)!} + k\cdot\frac{(n-1)!}{(n-k)!}\\ &=\frac{(n-1)! \cdot (n-k)}{(n-k)!} + k\cdot\frac{(n-1)!}{(n-k-1+1)!}\\ &=\frac{(n-1)!\cdot (n-k)}{(n-k-1)!\cdot(n-k)} + k\cdot \frac{(n-1)!}{((n-1)-(k-1))!}\\ &=\frac{(n-1)!}{((n-1)-k)!} + k\cdot \frac{(n-1)!}{((n-1)-(k-1))!}\\ &=(n-1)_k + k\cdot (n-1)_{k-1}\end{align}$$

Answer 2

$(n)_k-(n-1)_k=\frac{n!}{(n-k)!}-\frac{(n-1)!}{(n-k-1)!}=\frac{(n-1)!}{(n-k-1)!}(\frac{n}{n-k}-1)=\frac{(n-1)!}{(n-k-1)!}\times \frac{k}{n-k}=\frac{(n-1)!}{(n-k)!}\times k=k(n-1)_{k-1}$

Answer 3

Similarly to how exponents obey the rule $n^k=n\cdot n^{k-1}$, falling factorials obey the rules $$ (n)_k=n\cdot (n-1)_{k-1},\qquad (n)_k=(n-k+1)\cdot (n)_{k-1} $$ which hollow by pulling out either the first or last factor of $(n)_k$. Using these, $$ \begin{align} (n)_k &=n\cdot (n-1)_{k-1} \\&=[(n-k)+k](n-1)_{k-1} \\&=(n-k)\cdot (n-1)_{k-1} +k\cdot(n-1)_{k-1} \\&=(n-1)_k+k\cdot (n-1)_{k-1} \end{align} $$