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.
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?