Results 1 to 4 of 4

Math Help - Number Theory (2)

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    Number Theory (2)

    Find all n \in \mathbb{N} such that 4 \mid \binom{2n}{n}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2009
    Posts
    106
    Spoiler:


    4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Proof:

    Using n!! as the double factorial of n:

    \binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}

    2 \nmid (2n-1)!! and therefore 4 \mid \binom{2n}{n} if and only if d \le n-2, where d satisfies 2^d \mid \mid n! (that is, 2^d \mid n!, but 2^{d+1} \nmid n!).
    We'll use the fact that n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor} ( p prime) (Legendre's formula). The exponent of 2 in n! is:
    d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1
    Where the equality signs of \le are taken if and only if n is a power of two. Thus, d \le n-2 if and only if n is not a power of 2, and so 4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Q.E.D
    Last edited by Unbeatable0; December 8th 2009 at 06:51 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Unbeatable0 View Post
    Spoiler:


    4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Proof:

    Using n!! as the double factorial of n:

    \binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}

    2 \nmid (2n-1)!! and therefore 4 \mid \binom{2n}{n} if and only if d \le n-2, where d satisfies 2^d \mid \mid n! (that is, 2^d \mid n!, but 2^{d+1} \nmid n!).
    We'll use the fact that n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor} ( p prime) (Legendre's formula). The exponent of 2 in n! is:
    d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1
    Where the equality signs of \le are taken if and only if n is a power of two. Thus, d \le n-2 if and only if n is not a power of 2, and so 4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Q.E.D
    that's an unbeatable solution!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Quote Originally Posted by Unbeatable0 View Post
    Spoiler:


    4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Proof:

    Using n!! as the double factorial of n:

    \binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}

    2 \nmid (2n-1)!! and therefore 4 \mid \binom{2n}{n} if and only if d \le n-2, where d satisfies 2^d \mid \mid n! (that is, 2^d \mid n!, but 2^{d+1} \nmid n!).
    We'll use the fact that n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor} ( p prime) (Legendre's formula). The exponent of 2 in n! is:
    d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1
    Where the equality signs of \le are taken if and only if n is a power of two. Thus, d \le n-2 if and only if n is not a power of 2, and so 4 \mid \binom{2n}{n} if and only if n is not of the form 2^k.
    Q.E.D
    Wow! Where did you learn how to do all that?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  3. Number Theory (75)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 30th 2008, 07:14 AM
  4. Number Theory (4)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 30th 2008, 06:52 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum