Alright, so here's the first problem.

Prove that for all positive integers n, $\displaystyle \binom{2n}{n}< 4^n$.

This is what I have so far;

For n=1, $\displaystyle \frac{2n!}{n!n!} = \frac{2!}{1!1!} = 2 < 4^1 = 4^n.$

Assume this is true for some $\displaystyle n \in \mathbb{N}$. Now, for n+1,

$\displaystyle \frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)(2n !)}{(n+1)^2* n!*n!} < 4^n * \frac{(2n+2)(2n+1)}{(n+1)(n+1)}=4^n * \frac{(4n+2)}{(n+1)}$

That last part is where it is hazy.

Other problem I was having trouble with is,

Show for positive integers n,

$\displaystyle \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $.

I have a lot of crazy things for this so far. I think this, "$\displaystyle \sum_{k=0}^n \binom{n}{k}^2 = \sum_{k=0}^n \binom{n}{k}*\binom{n}{n-k}$" is the beginning of the way to take it, but I'm not sure.

Any help or new direction is greatly appreciated. Thanks a bunch in advance!