×

# Is it the correct Proof?

Last time I had an olympiad pretest and I was given an essay to solve this:

Let ${n \choose k} = \frac{n!}{(n-k)!k!}$. Prove that ${2n \choose n} \frac{1}{n+1}$ is an integer!

I can't figure it out during the test till I found out the proof in my rentroom. I also want to prove that any consecutive numbers are divisible by factorials of the number of the terms of the consecutive numbers.

My proof is:

Obviously, ${2n \choose n} \frac{1}{n+1} = \frac{(2n)!}{n!n!(n+1)} = \frac{(2n)(2n-1)(2n-2)..(n+2)(n+1)!}{n!(n+1)!}$

$=\frac{(2n)(2n-1)(2n-2)...(n+3)(n+2)}{n!}$

It is the same that we have to prove the new equations above. Let $$k$$ as an integer with $$k<n$$ so we define $$n=ak+r_{k}, 0 \leq r_{k} < k$$

Consider that n divides $$(2n)(2n-1)(2n-2)...(n+3)(n+2)$$. For $$k<n$$, Since there are $$n-1$$ consecutive terms and $$k<n$$, so it is divisible by $$k!$$ (includes proof of this)

With the help of modulo, we have $(n+2)(n+3)...(2n-1)(2n) \equiv (r_k +2)(r_k+3)...(2r_k-1)(2r_k) (\mod k)$

Obviously, the remainder of the consecutive terms also consecutives. Obviously for $$k<n$$ there will be at least a number which exceeds the remainder which has been agreed. Directly to remainders, we assume $$r_k+z = k$$ and so on. Since $$r_k+2 \leq r_k + z \leq 2r_k$$, obviously it is divisible by $$k$$. Consider this $(n+2)(n+3)...(2n-1)(2n) \equiv 0 (\mod n)$ $(n+2)(n+3)...(2n-1)(2n) \equiv 0 (\mod n-1)$ $...$ $(n+2)(n+3)...(2n-1)(2n) \equiv 0 (\mod 2)$ $(n+2)(n+3)...(2n-1)(2n) \equiv 0 (\mod 1)$

SInce the remainder of all of them are zero, multiplying all the equtions with the modulos are permittable. Thus $(n+2)(n+3)...(2n-1)(2n))^{n} \equiv 0 (\mod n!) \Rightarrow n+2)(n+3)...(2n-1)(2n) \equiv 0 (\mod n!)$

It concludes that ${2n \choose n} \frac{1}{n+1}$ is an integer.

Does the proof valid? Or any other ideas?

Note by Figel Ilham
1 year, 10 months ago

Sort by:

No, your conclusion is invalid. Check out Chinese Remainder Theorem to understand why you cannot just multiply the modulo terms together. For example, $$12 \equiv 0 \pmod{2}, 12 \equiv 0 \pmod{3}, 12 \equiv 0 \pmod{4}$$, but we do not have $$12 \equiv 0 \pmod{ 2 \times 3 \times 4 }$$.

If you don't recognize the number, check out Catalan Numbers. Staff · 1 year, 10 months ago

Comment deleted Oct 03, 2015

So, it is clear that $$( n+2) (n+3) \ldots (2n)$$ is multiple of $$(n-1) !$$. The issue is showing that it indeed is a multiple of $$n!$$. You can proceed by induction, and using the observation that $$\gcd (n, n+2) \leq 2$$, but the argument is slightly more convoluted.

There are also several other ways of doing so, most of which all motivated by Catalan Numbers. Staff · 1 year, 10 months ago

I'm also thinking by omitting the numerator primes which is indeed greater than the maximum primes on the denumerator. In conclusion, I omit the primes of $$2n$$ first consecutives which is greater than the largest prime of $$n$$ first consecutives and prove that it is indeed an integer. · 1 year, 10 months ago