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.

  • $\begingroup$ Is k in numerator multiplication or just like $n_{k}$ $\endgroup$ – Archis Welankar Jan 10 '16 at 5:55
  • 4
    $\begingroup$ 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?). $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.