Results 1 to 12 of 12

Math Help - My generalization to a problem , not sure it is true

  1. #1
    Super Member
    Joined
    Jan 2009
    Posts
    715

    My generalization to a problem , not sure it is true

    I am doing the past Putnam problems and one is

    Prove that  \frac{1}{n+1} \binom{2n}{n} is an integer .

    I make a generalization , which is :

     \frac{1}{n+k} \binom{2n}{n} is an integer iff  0 < k < \frac{x}{2} , where  x is the minimun prime factor of  n+k .

    If it is true , then the problem from Putnam is just a special case . However , I couldn't trust my proof so i beg for help here .

    Thanks



    p.s. I make use of floor function to prove it .

    EDIT: I find some errors in my statement , iff should be changed to if and the equality can hold . i.e.  0<k \leq\frac{x}{2}
    Last edited by simplependulum; May 16th 2010 at 01:46 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by simplependulum View Post
    I am doing the past Putnam problems and one is

    Prove that  \frac{1}{n+1} \binom{2n}{n} is an integer .

    I make a generalization , which is :

     \frac{1}{n+k} \binom{2n}{n} is an integer iff  0 < k < \frac{x}{2} , where  x is the minimun prime factor of  n+k .

    If it is true , then the problem from Putnam is just a special case . However , I couldn't trust my proof so i beg for help here .

    Thanks



    p.s. I make use of floor function to prove it .

    EDIT: I find some errors in my statement , iff should be changed to if and the equality can hold . i.e.  0<k \leq\frac{x}{2}
    I haven't taken the time to think about your real question yet, but I'd like to point out that

    <br />
\frac{1}{n+1} \binom{2n}{n}<br />

    is the nth catalan number. There are a numerous number of ways to show it is a integer .

    I will consider your question more in depth now...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    Posts
    95
    Thats false,

    take n=6 k=5. We have that n+k = 11, so x = 11. Clearly 5 <= 11/2, but the result is 216/5 as per n &#x3d; 6 k &#x3d;5, 1&#x2f;&#x28;n&#x2b;k&#x29; &#x2a;binom&#x28; 2&#x2a;n, n &#x29; - Wolfram|Alpha.

    I think thats a counter example ....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    95
    I think the easiest possible proof of the putnam question is to realize

    <br /> <br />
\frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}<br />
= \binom{2n}{n}-\binom{2n}{n+1}<br /> <br />
    Last edited by gmatt; May 17th 2010 at 03:11 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    actually there is a very simple way to generalize it :

    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(2n)!}{(2n - n)! k!}

    But obviously, 2n - n = n so :

    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(2n)!}{n! k!}

    And \frac{(2n)!}{n!} = (n + 1) \times (n + 2) \times \cdots \times 2n. So we are left with :

    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(n + 1) \times (n + 2) \times \cdots \times 2n}{k!}

    Thus :

    \frac{1}{n + k} \binom{2n}{n} = \frac{(n + 1) \times (n + 2) \times \cdots \times 2n}{(n + k)k!}

    Now we know that (n + k) has got to divide the top part of the fraction iff k \leqslant n. But we also know that each factor of k (not prime factor) will divide its double (which is present in the top part of the fraction since k \leqslant n).

    This leads to the conclusion that \frac{1}{n + k} \binom{2n}{n} is an integer for any k \leqslant n.

    Am I right ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Bacterius View Post
    Hello,
    actually there is a very simple way to generalize it :

    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(2n)!}{(2n - n)! k!}
    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(2n)!}{(2n - n)! n!}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by chiph588@ View Post
    \frac{1}{n + k} \binom{2n}{n} = \frac{1}{n + k} \times \frac{(2n)!}{(2n - n)! n!}
    oO

    what was that stupid mistake, guess I've seen too much k's these days. Thanks for noticing it though Chiph
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by gmatt View Post
    Thats false,

    take n=6 k=5. We have that n+k = 11, so x = 11. Clearly 5 <= 11/2, but the result is 216/5 as per n &#x3d; 6 k &#x3d;5, 1&#x2f;&#x28;n&#x2b;k&#x29; &#x2a;binom&#x28; 2&#x2a;n, n &#x29; - Wolfram|Alpha.

    I think thats a counter example ....
    You had a typo in your input. Your input I believe was read  \texttt{n=6k=5} instead of  \texttt{n=6, k=5}

    See here.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by simplependulum View Post
    I am doing the past Putnam problems and one is

    Prove that  \frac{1}{n+1} \binom{2n}{n} is an integer .

    I make a generalization , which is :

     \frac{1}{n+k} \binom{2n}{n} is an integer iff  0 < k < \frac{x}{2} , where  x is the minimun prime factor of  n+k .

    If it is true , then the problem from Putnam is just a special case . However , I couldn't trust my proof so i beg for help here .

    Thanks



    p.s. I make use of floor function to prove it .

    EDIT: I find some errors in my statement , iff should be changed to if and the equality can hold . i.e.  0<k \leq\frac{x}{2}
    Let  n=10 and  k=12

     n+k=22 = 2\cdot11\implies x=2

    But  12=k\not\leq \frac x2=1 and  \frac{1}{22} {20 \choose 10} = 8398

    I'm pretty sure this is a valid counterexample.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by chiph588@ View Post
    Let  n=10 and  k=12

     n+k=22 = 2\cdot11\implies x=2

    But  12=k\not\leq \frac x2=1 and  \frac{1}{22} {20 \choose 10} = 8398

    I'm pretty sure this is a valid counterexample.

    I think you may have something wrong here.

    Correct me if I am wrong but you are using the contrapositive to try to find a counter example.

    So let me restate the original proposition:
    the OP claims
    <br />
a \wedge b \implies c<br />

    where

    a is the logical statement k \le x/2
    b is the logical statement k > 0
    c is the logical statement \frac{1}{k+n}\binom{2n}{n} \text{ is an integer}

    thus the contrapositive is

    <br />
\neg c \implies \neg a \vee \neg b<br />

    thus we search for \frac{1}{k+n}\binom{2n}{n} \text{ is \textbf{not} an integer} and k \le x/2 for a counter example. I think....
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by gmatt View Post
    I think you may have something wrong here.

    Correct me if I am wrong but you are using the contrapositive to try to find a counter example.

    So let me restate the original proposition:
    the OP claims
    <br />
a \wedge b \implies c<br />

    where

    a is the logical statement k \le x/2
    b is the logical statement k > 0
    c is the logical statement \frac{1}{k+n}\binom{2n}{n} \text{ is an integer}

    thus the contrapositive is

    <br />
\neg c \implies \neg a \vee \neg b<br />

    thus we search for \frac{1}{k+n}\binom{2n}{n} \text{ is \textbf{not} an integer} and k \le x/2 for a counter example. I think....
    simplependulum proposed an if and only if statement. My counterexample only disproved one direction.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by chiph588@ View Post
    simplependulum proposed an if and only if statement. My counterexample only disproved one direction.
    Ahh yes, he added an edit at the bottom, he changed it from iff to an if.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Tube lemma generalization
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 27th 2010, 02:32 AM
  2. Continuity functions (Generalization)
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 28th 2010, 05:22 PM
  3. Erdos-Szekeres generalization
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 18th 2009, 03:35 AM
  4. Sandwich theorem generalization
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 4th 2009, 04:09 PM
  5. Apollonius Problem Generalization
    Posted in the Geometry Forum
    Replies: 0
    Last Post: June 22nd 2009, 07:49 AM

Search Tags


/mathhelpforum @mathhelpforum