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

Question

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}$$

Macro · Accepted Answer · 2012-04-27 18:09:49Z

up vote 3 down vote accepted

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$.

edited Apr 27 '12 at 18:09

answered Apr 27 '12 at 17:59

Macro
14.9k34693

	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

Erik · Answer 2 · 2012-04-27 17:58:23Z

up vote 5 down vote

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...

answered Apr 27 '12 at 17:58

Erik
1,583216

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

2 Answers