Sum the series : $\sum_{n\geq 1} \frac{C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)}{P(n,n)}$

Question

Sum the series $$\sum_{n\geq 1} \frac{C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)}{P(n,n)}$$

The answer is given as $e^2-1$. For getting that answer, $C(n,0)+C(n,1)+C(n,2)+\cdots+C(n,n)$ should be equal to $2^n$.
So how are they equal?

Answer 1

As you have correctly noted,

$$ \sum_{k=0}^n C(n,k) = 2^n $$ Furthermore, $P(n,n)=n!$, which allows us to rewrite your sum as

$$ \sum_{n\geq 1} \frac{2^n}{n!} $$ Now, notice that

$$ e^x = \sum_{n\geq 0} \frac{x^n}{n!} $$ So we write your sum as

$$ \left(\sum_{n\geq 0} \frac{2^n}{n!}\right)-1 $$ And using our definition of $e^x$ when $x=2$, we have the final result, $e^2-1$.

On the question of why $\sum_{k=0}^n C(n,k) = 2^n$, think of it this way:

$C(n,k)$ describes how many ways you can choose exactly $k$ objects from a set of $n$ objects. So, if you can think of it this way, it's like asking how many binary numbers you can form that have exactly $k$ ones.

To see this relationship, look at the case for $n=3$. Now you have a set, {1,2,3}, and you get $C(3,2)$ by counting how many ways you can choose two from the set of three. That is, 1+2, 1+3, and 2+3 for a total of 3.

But you can also write it like this: 110, 101, and 011... where 110 means "include objects 1 and 2, but not 3", and 011 means "include objects 2 and 3, but not 1". The number of 1s here has to be two, which is why 001 (one 1) and 111 (three 1s) don't appear.

You can do this for any number of objects, $n$. Now, the sum over all values of $k$ becomes the number of ways you can choose zero, plus choose 1, plus choose 2, plus choose 3, and so on. So it's actually "how many ways can we choose any number of objects from the set of $n$ objects?" And to answer this, consider that we can represent the numbers in that binary form... but we no longer care how many ones are in the number.

So 000, 001, 010, 011,... 110, 111 are all in the list. Essentially, you can take each "bit", and set it to either 1 or 0. So there's 2 options for each object, and thus $2^n$ options in total. So the sum is equal to $2^n$.