# A possible theorem

So i was playing around with members of a random power set, and i came to a revelation(at least to me it was). Say $A=\{1,2,3\}$ then for arbitrary $k,n\in Z^+$, $n=|A|$ and $\mathscr{P}(A)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$, $|\mathscr{P}(A)|=2^n.$ There are ${n\choose n-1}$ ways of choosing ($n-1$)- element sets in $\mathscr{P}(A)$ so that's ${3\choose1}+{3\choose2}+{3\choose3}=7$ so we're short by one, playing around once more and we have $2{n\choose n}+{n\choose n-1}+{n\choose n-2}=2^n$ and by generalizing: $2{n\choose n}+{n\choose k}+...+{n\choose k-(n-2)}=2^n$ for $1\le k\le n-1$.

Pardon my ignorance, but is there a theorem for this(if the equation is correct), and is this how research in math is done(if it is, then it must be pretty darn exciting!!!)

• Are you claiming that $2\binom{n}{n}+\binom{n}{n-1} + \binom{n}{n-2} = 2^n$ for all $n \in \Bbb Z_+$? – Siméon Dec 15 '13 at 17:46
• If they're not please show me some counter-examples – pkjag Dec 15 '13 at 17:56
• @pkjag ??? n=4. – Did Dec 15 '13 at 17:59
• But that's not my general formula, my main emphasis is on the last formula – pkjag Dec 15 '13 at 18:02
• What is ${n\choose k-(n-2)}$ if $k\leqslant n-1$? This seems to make sense only when $k=n-1$, in which case this is the formula in my answer, or when $k=n-2$, in which case this is wrong. – Did Dec 15 '13 at 18:05

## 1 Answer

The sums you suggest are not $2^n$ (maybe check a few simple cases?), the actual identity being $$\sum_{k=0}^n{n\choose k}=2^n.$$ This is a case of the binomial theorem, which states that $$\sum_{k=0}^n{n\choose k}x^k=(x+1)^n,$$ and, more generally, that $$\sum_{k=0}^n{n\choose k}x^ky^{n-k}=(x+y)^n.$$ Happy reading!

• Did did nice here! +1 – Namaste Dec 15 '13 at 17:50
• Did always does nice :P +1 – CODE Dec 15 '13 at 17:54
• So if wanted to show that the sums are equal to the number of elements in a power set would i need to generalize into the Binomial theorem, or could i create my own theorem to say so?? – pkjag Dec 15 '13 at 18:00
• @pkjag Did you read the WP page I linked to? – Did Dec 15 '13 at 18:02
• @Theta30 Because I am mean. Or the opposite. :-) – Did Dec 15 '13 at 18:06