Problem #1: Prove that $ nC0+nC1+\cdots+nCn = 2^n $ ($nCk$ denotes $n$ choose $k$).
Solution: Chances are you've seen this before, and there are many proofs to it (one of my favorites being the number of subsets of an $n$-element set... think about it).
But here's another cool proof, using our very own Binomial Theorem.
Consider $ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $.
But upon setting $x = 1$, we immediately have $2^n = nC0+nC1+\cdots+nCn $ as desired. QED.
--------------------
Problem #2: Prove that $ nC0-nC1+\cdots+(-1)^n(nCn) = 0 $.
Solution: Well if you understood the concept behind the first problem, this one should come very easily.
$ (x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn) $ so for $ x = -1 $ we have
$ 0 = (-1)^n(nC0)+(-1)^{n-1}(nC1)+\cdots+(nCn) $ from which we can just flip the sign (if necessary) to get the desired result. QED.
--------------------
Practice Problem #1: Prove $ nC0+nC1+\cdots+nCn = 2^n $ using the subsets argument.
Practice Problem #2: Show that $ nCr+nC(r+1) = (n+1)C(r+1)$.
Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides $200C100$.
1. nC0 is the number of subsets of a set of size n of size 0, nC1 is the number of subsets of size 1, ... to nCn the number of subsets of size n. Adding them gives the total number of subsets of a set of size n, which is 2^n because a subset either contains any given element or it does not. (This is assuming the empty set counts as a subset; if it doesn't, subtract nC0 = 1 from both sides.)
ReplyDelete2. A cheap sort of proof would be observing that this is equivalent to one method of generating Pascal's triangle. More rigorously:
(x+1)^n = nC0 + nC1 x^1 + ...
Multiply this series by (x+1) and look at the two terms that contribute to the coefficient of (n+1)C(r+1) x^{r+1}; the only two terms that do so are nCr x^r * x and nC(r+1) x^{r+1} * 1, so adding those together gives the desired result.
There's another cool subsets argument to #2: nCr is the number of r-element subsets of an n-element set. Suppose you add an element k. We want to find the number of (r+1)-element subsets in an (n+1)-element set. Consider the subsets with k and without k:
ReplyDeletewith k - nCr (take any r-elemnent subset of the original n-element set and add k - we now have r+1 elements)
without k - nC(r+1) (take any (r+1)-element subset of the original n-element set)
These two cases account for all the (r+1)-element subsets so we have our desired identity - nCr+nC(r+1) = (n+1)C(r+1).
#2: It's equivalent to saying that the sum of the two consecutive numbers in Pascal's triangle is equal to the number between them in the next row...
ReplyDeleteYeah, I know, not a very good proof, but you get the idea. :D
3. 200C100 = (200*199*198*...*101) / (100*99*...) = (2*199*2*197*...*101), so we want a two-digit prime that divides a three-digit odd number
ReplyDeleteStrange, it cut me off. Anyway, we have to multiply the prime by at least 3 to keep it odd, so the prime is
ReplyDelete61. wtf?
ReplyDelete