5
$\begingroup$

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!!!)

$\endgroup$
  • 1
    $\begingroup$ Are you claiming that $2\binom{n}{n}+\binom{n}{n-1} + \binom{n}{n-2} = 2^n$ for all $n \in \Bbb Z_+$? $\endgroup$ – Siméon Dec 15 '13 at 17:46
  • $\begingroup$ If they're not please show me some counter-examples $\endgroup$ – pkjag Dec 15 '13 at 17:56
  • $\begingroup$ @pkjag ??? n=4. $\endgroup$ – Did Dec 15 '13 at 17:59
  • $\begingroup$ But that's not my general formula, my main emphasis is on the last formula $\endgroup$ – pkjag Dec 15 '13 at 18:02
  • $\begingroup$ 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. $\endgroup$ – Did Dec 15 '13 at 18:05
5
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Did did nice here! +1 $\endgroup$ – Namaste Dec 15 '13 at 17:50
  • $\begingroup$ Did always does nice :P +1 $\endgroup$ – CODE Dec 15 '13 at 17:54
  • $\begingroup$ 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?? $\endgroup$ – pkjag Dec 15 '13 at 18:00
  • $\begingroup$ @pkjag Did you read the WP page I linked to? $\endgroup$ – Did Dec 15 '13 at 18:02
  • $\begingroup$ @Theta30 Because I am mean. Or the opposite. :-) $\endgroup$ – Did Dec 15 '13 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.