6
$\begingroup$

I have trouble understanding what I'm supposed to do in some of these math questions. Here's an exam question from an old exam:

Let $A$ be a set with $n$ elements. The number of subsets of $A$ with $k$ elements is ${n \choose k}$, or: $$ C(n,k) = \frac{n!}{k!(n - k)!} $$ Show that there are as many subsets having an odd number of elements as there are subsets with an even number of elements. HINT: use the Binomial Theorem in the form: $$ (1 + x)^n = \sum_{k = 0}^n {n \choose k} x^k$$ Then set $x = -1$.

Do I just choose an arbitrary number for $n$ then set $x = -1$ and work it out? I don't know why I have such a problem understanding these questions. Thanks for your help.

$\endgroup$
2
  • $\begingroup$ Try writing out the formula with $x$ replaced by $-1$, and simplifying a bit. You can even choose some (small, but not too small) value of $n$ if you want to be completely concrete. This might give you a clue as to what is going on in the general case. $\endgroup$ – mdp Jan 9 '13 at 10:27
  • $\begingroup$ Thank you for your help Matt. $\endgroup$ – mal Jan 10 '13 at 14:09
3
$\begingroup$

If you set $x=-1$ in your formula, then $$ 0=(1+(-1))^n=\sum_{k=0}^n\binom{n}{k}(-1)^k, $$ or splitting up the sum in positive and negative parts $$ 0=\sum_{\substack{k=0 \\k\text{ even}}}^n \binom{n}{k}+\sum_{\substack{k=0 \\k\text{ odd}}}^n\binom{n}{k}(-1), $$ or equivalently $$ \sum_{\substack{k=0 \\k\text{ odd}}}^n\binom{n}{k}=\sum_{\substack{k=0 \\k\text{ even}}}^n\binom{n}{k}. $$ Note that $$ \sum_{\substack{k=0 \\k\text{ even}}}^n\binom{n}{k}=\binom{n}{0}+\binom{n}{2}+\cdots $$ is exactly the number ways to take out a subset of even size out of a set with $n$ elements and similarly with $k$ odd.

$\endgroup$
1
  • $\begingroup$ You're welcome. $\endgroup$ – Stefan Hansen Jan 10 '13 at 14:08
4
$\begingroup$

You start with the set $A$ which cardinality is $n$. The number of subsets of $A$ with odd cardinalities is $$ \sum_{k:\text{ odd}}{n \choose k} $$ and with even cardinalities is $$ \sum_{k:\text{ even}}{n \choose k} $$ so their difference is $$ \sum_{k:\text{ even}}{n \choose k} - \sum_{k:\text{ odd}}{n \choose k} = \sum_{0\leq k\leq n}{n \choose k}(-1)^k = (1+(-1))^n = 0 $$

$\endgroup$
2
  • $\begingroup$ Thank you for your help Ilya; I know your answer has the most votes, but I gave the correct mark to Stefan Hansen as I found that answer easier to comprehend. Once that clicked then your answer made sense to me. I think it was the $ 0 <= k <= n $ that threw me off. Thanks again though. $\endgroup$ – mal Jan 10 '13 at 14:05
  • $\begingroup$ @mal: you're welcome of course! And don't feel necessary to explain - that's only your choice which answer is better exactly for you. $\endgroup$ – Ilya Jan 10 '13 at 14:18
3
$\begingroup$

Hint: Don't use the hint.

We assume (necessarily) that $n\ge 1$ and let $a$ be an element of $A$. There is an obvious bijection between a) the odd sets containing $a$ and the even sets not containing $a$ (drop $a$ from the set) and b) the odd sets not containing $a$ and the even sets containing $a$ (add $a$ to the set). Together this gives a bijection of odd and even sets, especially the numbers are the same.

$\endgroup$
6
  • 2
    $\begingroup$ I have had teachers who mark you wrong if you don't use their hint ... $\endgroup$ – Calvin Lin Jan 9 '13 at 10:42
  • $\begingroup$ @CalvinLin: Understanding a particular given solution to the problem sometimes is more important than coming up with the one by yourself. $\endgroup$ – Ilya Jan 9 '13 at 10:44
  • $\begingroup$ @Ilya I agree with you, esp since you may not know where the teacher is coming from. The comment was made with regards to "Hint: Don't use the hint." $\endgroup$ – Calvin Lin Jan 9 '13 at 11:27
  • 1
    $\begingroup$ @Calvin: Such teachers are incompetent. Yes, one still has to decide how to deal with them, and one may decide that it’s easiest to go along, but they’re still incompetent. (I’d be delighted if a student found an independent solution.) $\endgroup$ – Brian M. Scott Jan 9 '13 at 15:05
  • $\begingroup$ I think one should distinguish between hints and explicit demands to use a specific tool (e.g. show $\frac{\sin x}x\to 1$ using Taylor series / l'Hospital / the definition of derivative / the geometric area of a circular segment; it may be instructive to try all these ways). Then again, hints are usually more valuable to accept than to ignore, esp. things like "for part (b) use part (a)". $\endgroup$ – Hagen von Eitzen Jan 9 '13 at 15:28

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.