# Thread: Need Help w/ Two Proofs.

1. ## Need Help w/ Two Proofs.

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!

2. For the first problem, $\displaystyle 2n\choose n$ is the number of subsets of size n, while $\displaystyle 2^{2n}$ is the number of all subsets.

For the second problem, see equation (8) on this Wikipedia page for an algebraic proof. A little further, it also has a combinatorial proof.

3. I saw that for the first problem. Do you think they require a formal proof in a combinatorics class?

4. Do you think they require a formal proof in a combinatorics class?
Many facts have both algebraic and combinatorial proofs. The latter are perfectly rigorous and legitimate. After all, the binomial coefficients are usually defined as the number of subsets, not through factorials. Sometimes, though, instructors explicitly require one type of proof or the other. Unless it is explicitly stated, I believe both types are legitimate (and I think that combinatorial proofs are often more elegant).

You almost finished the algebraic proof.
Originally Posted by bakerconspiracy
$\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)}$
Just note that $\displaystyle 4^n\frac{(4n+2)}{(n+1)}<4^n\frac{(4n+4)}{(n+1)}=4^ {n+1}$

5. Originally Posted by emakarov
(and I think that combinatorial proofs are often more elegant).
I better go look up how to do these combinatoric proofs. It just doesn't feel right stating everything, but I see your point.

Originally Posted by emakarov
You almost finished the algebraic proof.
Just note that $\displaystyle 4^n\frac{(4n+2)}{(n+1)}<4^n\frac{(4n+4)}{(n+1)}=4^ {n+1}$
Ahh thanks so much. Was lacking clarity last night.