I have the following sum:
$$\sum_{n=1}^k \frac{k!}{n!(k-n)!}, \quad k=9$$
It got simplified to $2^k-1$. How can I do it with math formulas? Thank you!
Asked
Active
Viewed 2,343 times
2
Thomas Andrews
- 177,126
Chelios
- 123
-
3The function $\dfrac{k!}{n!(k-n)!}$ is often written $\binom k n$, and is called the binomial coefficient. – Thomas Andrews Jul 11 '13 at 14:59
2 Answers
9
Use the binomial theorem, which states:
$$ \sum_{n=0}^k a^n b^{k-n} \frac{k!}{n!(k-n)!} = (a+b)^k $$
Use $a=b=1$, that is where the $2^k$ comes from.
The -1 is because the theorem includes the term when $n=0$, whereas in your question the summation only starts at $n=1$. So you must subtract the term when $n=0$, which is $1$, hence $-1$.
So $2k-1$.
gnoodle
- 13
- 3
Umberto P.
- 52,165
2
$$\frac{k!}{n!(k-n)!}=\binom{k}{n},\binom{k}{0}=1$$ $$\sum_{n=0}^k\binom{k}{n}=2^k$$ $$\sum_{n=1}^k \frac{k!}{n!(k-n)!}=-1+\binom{k}{0}+\sum_{n=1}^k \binom{k}{n}=-1+\sum_{n=0}^k\binom{k}{n}=-1+2^k$$
Adi Dani
- 16,949