A possible theorem

Question

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
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
No we are not "okay" (and you seem quite intent in NOT reading the page I linked to). — Did, Dec 15 '13 at 18:17
So if i add the clause 'for all $n\lt4$' can it be made into a theorem then?? — pkjag, Dec 15 '13 at 18:25

Did · Accepted Answer · 2013-12-15T17:56:47.953

5

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!

edited Dec 15 '13 at 17:56

answered Dec 15 '13 at 17:47

Did

279,727

1

Did did nice here! +1 – amWhy 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
@Theta30 am a he, while it may not be a new theorem, the experience was golden – pkjag Dec 15 '13 at 18:07

A possible theorem

1 Answers1