1
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I understand, I probably didn't pay attention, that's why I got the wrong results. $\endgroup$ Apr 7, 2016 at 9:36

Not the answer you're looking for? Browse other questions tagged .