Results 1 to 4 of 4

Thread: Number Theory (2)

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    Number Theory (2)

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

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


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

    Using $\displaystyle n!!$ as the double factorial of $\displaystyle n$:

    $\displaystyle \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!}$

    $\displaystyle 2 \nmid (2n-1)!!$ and therefore $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle d \le n-2$, where $\displaystyle d$ satisfies $\displaystyle 2^d \mid \mid n!$ (that is, $\displaystyle 2^d \mid n!$, but $\displaystyle 2^{d+1} \nmid n!$).
    We'll use the fact that $\displaystyle n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ($\displaystyle p$ prime) (Legendre's formula). The exponent of $\displaystyle 2$ in $\displaystyle n!$ is:
    $\displaystyle 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 $\displaystyle \le$ are taken if and only if $\displaystyle n$ is a power of two. Thus, $\displaystyle d \le n-2$ if and only if $\displaystyle n$ is not a power of $\displaystyle 2$, and so $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle n$ is not of the form $\displaystyle 2^k$.
    Q.E.D
    Last edited by Unbeatable0; Dec 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:


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

    Using $\displaystyle n!!$ as the double factorial of $\displaystyle n$:

    $\displaystyle \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!}$

    $\displaystyle 2 \nmid (2n-1)!!$ and therefore $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle d \le n-2$, where $\displaystyle d$ satisfies $\displaystyle 2^d \mid \mid n!$ (that is, $\displaystyle 2^d \mid n!$, but $\displaystyle 2^{d+1} \nmid n!$).
    We'll use the fact that $\displaystyle n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ($\displaystyle p$ prime) (Legendre's formula). The exponent of $\displaystyle 2$ in $\displaystyle n!$ is:
    $\displaystyle 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 $\displaystyle \le$ are taken if and only if $\displaystyle n$ is a power of two. Thus, $\displaystyle d \le n-2$ if and only if $\displaystyle n$ is not a power of $\displaystyle 2$, and so $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle n$ is not of the form $\displaystyle 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:


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

    Using $\displaystyle n!!$ as the double factorial of $\displaystyle n$:

    $\displaystyle \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!}$

    $\displaystyle 2 \nmid (2n-1)!!$ and therefore $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle d \le n-2$, where $\displaystyle d$ satisfies $\displaystyle 2^d \mid \mid n!$ (that is, $\displaystyle 2^d \mid n!$, but $\displaystyle 2^{d+1} \nmid n!$).
    We'll use the fact that $\displaystyle n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ($\displaystyle p$ prime) (Legendre's formula). The exponent of $\displaystyle 2$ in $\displaystyle n!$ is:
    $\displaystyle 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 $\displaystyle \le$ are taken if and only if $\displaystyle n$ is a power of two. Thus, $\displaystyle d \le n-2$ if and only if $\displaystyle n$ is not a power of $\displaystyle 2$, and so $\displaystyle 4 \mid \binom{2n}{n}$ if and only if $\displaystyle n$ is not of the form $\displaystyle 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: Jul 8th 2011, 06:09 PM
  2. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  3. Number Theory (75)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 30th 2008, 07:14 AM
  4. Number Theory (4)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 30th 2008, 06:52 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum