My generalization to a problem , not sure it is true

**simplependulum** · May 15th 2010, 10:47 PM

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}$

**gmatt** · May 17th 2010, 09:23 AM

Originally Posted by simplependulum

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

$ \frac{1}{n+1} \binom{2n}{n} $

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...

**gmatt** · May 17th 2010, 10:12 AM

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 = 6 k =5, 1/(n+k) *binom( 2*n, n ) - Wolfram|Alpha.

I think thats a counter example ....

**gmatt** · May 17th 2010, 11:32 AM

I think the easiest possible proof of the putnam question is to realize

$ \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1} = \binom{2n}{n}-\binom{2n}{n+1} $

**Bacterius** · May 17th 2010, 01:09 PM

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 ?

**chiph588@** · May 17th 2010, 01:26 PM

Originally Posted by Bacterius

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

**Bacterius** · May 17th 2010, 07:53 PM

Originally Posted by chiph588@

$\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

**chiph588@** · May 17th 2010, 09:47 PM

Originally Posted by gmatt

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 = 6 k =5, 1/(n+k) *binom( 2*n, n ) - 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.

**chiph588@** · May 18th 2010, 08:55 AM

Originally Posted by simplependulum

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.

**gmatt** · May 18th 2010, 12:47 PM

Originally Posted by chiph588@

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
$ a \wedge b \implies c $

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

$ \neg c \implies \neg a \vee \neg b $

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....

**chiph588@** · May 18th 2010, 12:52 PM

Originally Posted by gmatt

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
$ a \wedge b \implies c $

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

$ \neg c \implies \neg a \vee \neg b $

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.

**gmatt** · May 18th 2010, 01:11 PM

Originally Posted by chiph588@

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.

Thread: My generalization to a problem , not sure it is true

LinkBack

Thread Tools

Display

My generalization to a problem , not sure it is true

Similar Math Help Forum Discussions

Tube lemma generalization

Continuity functions (Generalization)

Erdos-Szekeres generalization

Sandwich theorem generalization

Apollonius Problem Generalization

Search Tags