Results 1 to 5 of 5

Math Help - Need Help w/ Two Proofs.

  1. #1
    Newbie bakerconspiracy's Avatar
    Joined
    Mar 2009
    Posts
    20

    Need Help w/ Two Proofs.

    Alright, so here's the first problem.

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

    This is what I have so far;

    For n=1, \frac{2n!}{n!n!} = \frac{2!}{1!1!} = 2 < 4^1 = 4^n.
    Assume this is true for some n \in \mathbb{N}. Now, for n+1,
    \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,

    \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, " \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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    For the first problem, 2n\choose n is the number of subsets of size n, while 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie bakerconspiracy's Avatar
    Joined
    Mar 2009
    Posts
    20
    I saw that for the first problem. Do you think they require a formal proof in a combinatorics class?

    Thanks, I must have over looked that on the wikipedia page.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    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.
    Quote Originally Posted by bakerconspiracy View Post
    \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 4^n\frac{(4n+2)}{(n+1)}<4^n\frac{(4n+4)}{(n+1)}=4^  {n+1}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie bakerconspiracy's Avatar
    Joined
    Mar 2009
    Posts
    20
    Quote Originally Posted by emakarov View Post
    (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.

    Quote Originally Posted by emakarov View Post
    You almost finished the algebraic proof.
    Just note that 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 04:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 08:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 08:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 05:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 03:01 PM

/mathhelpforum @mathhelpforum