Waste less time on Facebook — follow Brilliant.

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

No vote yet
1 vote


Sort by:

Top Newest

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. Calvin Lin Staff · 1 year, 10 months ago

Log in to reply

Comment deleted Oct 03, 2015

Log in to reply

@Figel Ilham 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. Calvin Lin Staff · 1 year, 10 months ago

Log in to reply

@Calvin Lin 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. Figel Ilham · 1 year, 10 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...