Exercise Lover

March 23, 2007

Exercises C.1-15

Filed under: C.1 — yuhanlyu @ 5:03 am

Let f(x) = \sum^n_{k=0} {n \choose k} x^k = (1+x)^n
f’(x) = \sum^n_{k=0} {n \choose k} kx^{k-1} = n(1+x)^{n-1}
Replace x by 1, then we get \sum^n_{k=0} {n \choose k} k = n2^{n-1}

Exercises C.1-14

Filed under: C.1 — yuhanlyu @ 4:59 am

H'(\lambda) = -\log \frac{\lambda}{1-\lambda}
if \lambda = 0.5, then H achieves the maximum value, which is 1.

Exercises C.1-13

Filed under: C.1 — yuhanlyu @ 4:51 am

{2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{\sqrt{4\pi n}{\frac{2n}{e}}^{2n}(1+O(1/n))}{2\pi n {\frac{n}{e}}^{2n}(1+O(1/n)} = \frac{2^{2n}}{\sqrt{\pi n}}(1+O(1/n))

Exercises C.1-12

Filed under: C.1 — yuhanlyu @ 4:42 am

Proof by induction.
Base case: {n \choose 0} \leq 1 .
Induction step: Assume that {n \choose h} \leq \frac{n^n}{h^h(n-h)^{n-h}} is true for all h < k.
Then {n \choose k} = \frac{n-k+1}{k} {n \choose k-1} \leq \frac{n-k+1}{k} \frac{n^n}{(k-1)^{k-1}(n-k+1){n-k+1}} \leq \frac{n^n}{k^k(n-k)^{n-k}} if k < n/2

Exercises C.1-11

Filed under: C.1 — yuhanlyu @ 4:27 am

{n \choose j+k} = \frac{n!}{(j+k)!(n-j-k)!} \leq \frac{n!}{j!k!(n-j-k)!} = {n \choose j}{n-j \choose k}.

If we want to count the ways to choose the j+k items from n items. We can first choose j items from n items, then choose k items from remainder n-j items. But in this way may, the are some equal choosing methods counted many times. Hence this way is the upper bound for original problem.

March 22, 2007

Exercises C.1-10

Filed under: C.1 — yuhanlyu @ 11:39 am

Since the ratio of kth binomial coefficient and (k+1)-th is \frac{n-k+1}{k}. As long as the ratio is greater than 1, then the binomial coefficient may grow larger. So when k = \lfloor n/2 \rfloor or \lceil n/2 \rceil is the maximum value.

March 21, 2007

Exercises C.1-9

Filed under: C.1 — yuhanlyu @ 1:15 pm

Proof by induction.
Base case: 1 = 2 \choose 2.
Induction step: Assume \sum^n_{i=1} i = {n+1 \choose 2} for all n < k. Then \sum^k_{i=1} i = \sum^{k-1}_{i=1} i + k = {k \choose 2} + k = {k+1 \choose 2}.

Exercises C.1-8

Filed under: C.1 — yuhanlyu @ 12:52 pm

Exercises C.1-7

Filed under: C.1 — yuhanlyu @ 12:51 pm

Combinatorial interpretation.
If we want to choose k objects from n objects. There are two cases. The first object is choosen and the first object is not choosen. Hence {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.

Exercises C.1-6

Filed under: C.1 — yuhanlyu @ 12:48 pm

{n \choose k} = \frac{n!}{k!(n-k)!} = \frac{n}{n-k} \frac{(n-1)!}{k!(n-k-1)!} = \frac{n}{n-k} {n-1 \choose k}

Older Posts »

Blog at WordPress.com.