# How do I solve $C_x^0 + C_x^1 + \cdots + C_x^n = 2^n$ [duplicate]

I have the following equation, where I need to calculate x.

$$C_x^0 + C_x^1 + \cdots + C_x^n = 2^n$$

I have expanded this to

$$\frac{x!}{0! \times x!} + \frac{x!}{1! \times \left(x - 1\right)!} + \cdots + \frac{x!}{\times \left( x - n \right)!} = 2^n$$

Which can be rewritten as

$$\sum_{k=0}^n \frac{x!}{k! \times \left(x - k \right)!} = 2^n$$

I got stuck here, so I tried to calculate $x$ for $n$ from $0$ to $3$.

For $n = 0$ $$\frac{x!}{0! \times x!} = 1 \iff 1 = 1 \;\text{True for any  x \in \Bbb N }$$

For $n = 1$ $$\frac{x!}{0! \times x!} + \frac{x!}{\times \left( x - 1 \right)!} = 2 \implies x = 1$$

For $n = 2$ $$\frac{x!}{0! \times x!} + \frac{x!}{1! \times \left( x - 1 \right)!} + \frac{x!}{2! \times \left( x-2 \right)!} = 4 \implies x \in \{2, - 3\} \implies x = 2$$

For $n = 3$ $$\frac{x!}{0! \times x!} + \frac{x!}{1! \times \left( x - 1 \right)!} + \frac{x!}{2! \times \left( x-2 \right)!} + \frac{x!}{\times \left( x - 3 \right)!} = 8 \implies x^3 + 5x = 42 \implies x = 3$$

Did I do any mistakes so far? How would I go about calculating the general formula?

EDIT: Revised and got the right answers.

• just expand $2^n=(1+1)^n = \sum_{i=1}^{n} \binom{i}{n}$ and conclude $x=n$ Apr 7, 2016 at 9:28
• @K.K.McDonald: Not quite -- one also has to argue that the solution is unique, and this isn't the case for $n=0$. Apr 7, 2016 at 9:29
• yup that's right. thanks for feed back Apr 7, 2016 at 9:34

The left-hand side counts the number of subsets of up to $n$ elements of a set of $x$ elements, and the right-hand side is the total number of subsets of a set of $n$ elements, so the equation is satisfied by $x=n$. This solution is unique since the left-hand side is strictly increasing in $x$, unless $n=0$, in which case as you found any $x$ satisfies the equation.
Your solutions for $n=2$ and $n=3$ are wrong, but since you didn't show how you arrived at them, there's nothing more to say about why.