# Simplify sum of combinations with same n, all possible values of k

Is there a way to simplify this equation?

$$\dbinom{8}{1} + \dbinom{8}{2} + \dbinom{8}{3} + \dbinom{8}{4} + \dbinom{8}{5} + \dbinom{8}{6} + \dbinom{8}{7} + \dbinom{8}{8}$$

Or more generally,

$$\sum_{k=1}^{n}\dbinom{n}{k}$$

-

See

which says

$$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

You can prove this using the binomial theorem where $x=y=1$.

Now, since $\binom{n}{0} = 1$ for any $n$, it follows that

$$\sum_{k=1}^{n} \binom{n}{k} = 2^n - 1$$

In your case $n=8$, so the answer is $2^8 - 1 = 255$.

-
Thanks. I was trying to figure out all the possible sets of input features for a regression, so my mind start with statistics but I suppose this question is not stats per se. –  idris Apr 27 '12 at 18:00
No problem. Please consider upvoting and/or accepting answers you've found helpful :) –  Macro Apr 27 '12 at 18:08
Of course. Also I believe your i's should be k's. –  idris Apr 27 '12 at 18:09
you're right - fixed. –  Macro Apr 27 '12 at 18:09

Homework?

Hint:

Remember the binomial theorem:

$$(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$$

Now, if you could just find x and y so that $x^ky^{n-k}$ is constant...

-
that's a really great hint. Thanks –  idris Apr 27 '12 at 18:17