How to show that 2nCn <= 2^2n?
Suppose you have a set with 2n elements. How many subsets can we form? 2^{2n} = 4^n.
Now how many subsets, each containing exactly n elements, can we form? This number is {2n choose n}.
In the first statement above, we considered all subsets (not just those with n elements), and so 4^n is greater than or equal to {2n choose n}.
Thank you, but can u tell me how to prove it by induction?
To show that 2nCn ≤ 2^(2n), we need to prove it using mathematical induction.
Induction Step:
We assume that the inequality holds for some positive integer k. That is, we assume 2kCk ≤ 2^(2k).
Now, we need to show that the inequality also holds for k+1. That is, we need to show 2(k+1)C(k+1) ≤ 2^(2(k+1)).
Using the binomial coefficient formula, we can express 2(k+1)C(k+1) as (2k+2)! / ((k+1)!(k+1)!).
Similarly, we can express 2^(2(k+1)) as 2^(2k+2) = 4*2^(2k).
To compare both expressions, we can simplify 2(k+1)C(k+1) as (2k+2)(2k+1)! / ((k+1)!(k+1)).
Expanding the factorials, we get (2k+2)(2k+1)(2k)! / (k+1)(k)!(k+1).
Canceling out some terms, we have (2k+2)(2k+1)/(k+1).
Since (2k+2)/(k+1) ≤ 2, and (2k+1) ≤ (2k+2), we can conclude that (2k+2)(2k+1)/(k+1) ≤ 2*2 = 4.
This shows that 2(k+1)C(k+1) ≤ 4 * (2k)!, and by our induction assumption, we have (2k)! ≤ 2^(2k).
Therefore, we can substitute and conclude that 2(k+1)C(k+1) ≤ 4 * 2^(2k) = 2^(2(k+1)).
Thus, by mathematical induction, we have shown that 2nCn ≤ 2^(2n) for all positive integers n.