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

1. ## My generalization to a problem , not sure it is true

I am doing the past Putnam problems and one is

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

I make a generalization , which is :

$\displaystyle \frac{1}{n+k} \binom{2n}{n}$ is an integer iff $\displaystyle 0 < k < \frac{x}{2}$ , where $\displaystyle x$ is the minimun prime factor of $\displaystyle 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. $\displaystyle 0<k \leq\frac{x}{2}$

2. Originally Posted by simplependulum
I am doing the past Putnam problems and one is

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

I make a generalization , which is :

$\displaystyle \frac{1}{n+k} \binom{2n}{n}$ is an integer iff $\displaystyle 0 < k < \frac{x}{2}$ , where $\displaystyle x$ is the minimun prime factor of $\displaystyle 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. $\displaystyle 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

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

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

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

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

5. Hello,
actually there is a very simple way to generalize it :

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

But obviously, $\displaystyle 2n - n = n$ so :

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

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

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

Thus :

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

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

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

Am I right ?

6. Originally Posted by Bacterius
Hello,
actually there is a very simple way to generalize it :

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

7. Originally Posted by chiph588@
$\displaystyle \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

8. 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 &#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 $\displaystyle \texttt{n=6k=5}$ instead of $\displaystyle \texttt{n=6, k=5}$

See here.

9. Originally Posted by simplependulum
I am doing the past Putnam problems and one is

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

I make a generalization , which is :

$\displaystyle \frac{1}{n+k} \binom{2n}{n}$ is an integer iff $\displaystyle 0 < k < \frac{x}{2}$ , where $\displaystyle x$ is the minimun prime factor of $\displaystyle 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. $\displaystyle 0<k \leq\frac{x}{2}$
Let $\displaystyle n=10$ and $\displaystyle k=12$

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

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

I'm pretty sure this is a valid counterexample.

10. Originally Posted by chiph588@
Let $\displaystyle n=10$ and $\displaystyle k=12$

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

But $\displaystyle 12=k\not\leq \frac x2=1$ and $\displaystyle \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
$\displaystyle a \wedge b \implies c$

where

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

thus the contrapositive is

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

thus we search for $\displaystyle \frac{1}{k+n}\binom{2n}{n} \text{ is \textbf{not} an integer}$ and $\displaystyle k \le x/2$ for a counter example. I think....

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

where

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

thus the contrapositive is

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

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

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