# identity with falling factorials

How can one show that $$\sum_{k=0}^n \frac{(n)_k}{k!} = 2^n$$ for all $n \geq 0$ where for $m \in \mathbb{Z}$ and $k \geq 0$ $(m)_k$ is the "falling factorial": $$(m)_k = \begin{cases} 1, &\text{if }k = 0 \\ m ( m-1 ) \cdots ( m - ( k-1)), &\text{if }k > 0\end{cases}$$

I thought this would be induction, but I haven't been able to figure out how to do it.

• Is k in numerator multiplication or just like $n_{k}$ – Archis Welankar Jan 10 '16 at 5:55
• Note that $\frac{(n)_k}{k!} \equiv {n\choose k}$ the binomial coefficient. Many ways to proceed here: you can for example prove it by induction or you can give a combinatorial proof (what is the sum counting?). – Winther Jan 10 '16 at 5:59

By the binomial theorem, $$2^n=(1+1)^n=\sum_{k=0}^n{ n \choose k}$$
Can you see why this sum and your sum are equal? What's the definition of $(n)_{k}$ in terms of factorials?