# Proof that (2n)!/[n!(n+1)!] is natural for natural n

1. Sep 26, 2004

### pig

f(n+1) = 4f(n) - 6f(n)/(n+2)

So now I'd have to prove that 6*(2n)!/[n!(n+1)!(n+2)] is natural, which would be going in circles.

I tried to go directly, but came up with nothing good. It can be written as [2n over (n-1)] / n, but I still didn't manage to prove it.

Can anyone help?

By the way, I got this problem from a high school kid who was supposed to prove it by induction, so I presume I'm missing something obvious here?

Thanks.

2. Sep 26, 2004

### phoenixthoth

Let B(n,k) be the usual binomial coefficient: n!/[k!(n-k)!].

B(2n,n)=(2n)!/[n!(2n-n)!]=(2n)!/[n!n!]=(n+1)(2n)!/[n!(n+1)!]=(n+1)f(n)

f(n)=B(2n,n)/(n+1).

f(n)=B(2n,n)=2n(2n-1)...(n+1)n/(n+1)=2n(2n-1)...(n+2)n.

Last edited: Sep 26, 2004
3. Sep 26, 2004

### robert Ihnot

This series of numbers is called Catalan numbers: 1,2,5,14,42,132,492..and represent, among other things, the number of ways that votes of Yes or No can be counted if the vote is evenly split and the yes's are never behind in the counting. For example for 4 voters
we have: YYNN and YNYN.

This is equal to $$\frac{4!}{2!3!}=2$$

See: http://www-gap.dcs.st-and.ac.uk/~history/Miscellaneous/CatalanNumbers/catalan.html

Last edited: Sep 26, 2004
4. Sep 26, 2004

### pig

Thank you but I don't really seem to get this...

f(n) = B(2n, n)/(n+1)

I got this and didn't know what do do with it... B(2n, n) isn't:
2n(2n-1)...(n+1)n
It's:
2n(2n-1)...(n+1)/(1*2*3*4*...*n)
So we get, for f(n):
2n(2n-1)...(n+2)/(1*2*3*4*...*n)
Which is B(2n, n-1)/n

I think

Robert thank you for the information, I'll try to google a proof.

Last edited: Sep 26, 2004
5. Sep 26, 2004

### robert Ihnot

This is from the internet: The Catalan Numbers also turn up in Pascal's Triangle. If one takes the element in Pascal's Triangle given by the binomial coefficient (2n!)/(n!n!) and subtracts the adjacent element (2n!)/[(n+1)!(n-1)!] the result is the Nth Catalan Number.

http://www.saintanns.k12.ny.us/depart/math/Seth/intro.html

Last edited: Sep 27, 2004
6. Sep 26, 2004

### geometer

I think we're trying to make this way too complicated. Here is an induction proof:

1. Show that it is true for n=1. And it is, for n=1 we get 2n!/n!(n+1)! = 1 Which is a natural number

2. Now, we show that if it is true for k, where k is any natural number, it is true for k+1.

3. For k+1 we get, 2(k+1)!/(k+1)!(k+2)! = 2(k+1)k!/(k+1)k!(k+1)(k+1)! = 2k!/k!(k+1)! (look carefully at all the factors of (k+1) and see how they cancel)

4. Since we have now shown that it is true for n =1 and if it is true for k, it is also true for k+1, then by the principle of induction it is true for all natural numbers.

Last edited: Sep 26, 2004
7. Sep 26, 2004

### pig

This also looks wrong to me, but it's too late now, I'll look more closely tomorrow.

8. Sep 26, 2004

### Muzza

It is indeed wrong, 2(k+1)!/((k+1)!(k+2)!) = 2(k+1)k!/((k+1)k!(k+2)(k+1)!).

9. Sep 27, 2004

### geometer

Yep, you're right. In fact, it's wrong on a couple levels. My sincere apologies. I will more carefully check my posts before posting them in the future!

10. Sep 27, 2004

### pig

Ok I made some progress but it still isn't complete:

(a over b means the binominal coefficient)

(2n!)/[n!(n+1)!]
= (2n)!/[n!n!(n+1)]
= (2n)!(n+1-n)/[n!n!(n+1)]
= [(2n!)(n+1) - (2n!)n]/[n!n!(n+1)]
= (2n!)(n+1)/[n!n!(n+1)] - (2n!)n/[n!n!(n+1)]
= (2n!)/(n!n!) - (2n!)/[(n-1)!(n+1)!]
= (2n!)/(n!n!) - (2n!)/[(n-1)!(2n-n+1)!]
= (2n over n)-(2n over n-1)

Now, (2n over n-1)=(2n over n) * n/(n+1)

Since n/(n+1) < 1, (2n over n-1) < (2n over n) so (2n over n)-(2n over n-1) > 0, so this proves positivity.

But for this to work I still need to prove that the binominal coefficient itself is natural Anyone? I have a feeling this could even be a "textbook proof"... And google refuses to give me anything useful these days

Last edited: Sep 27, 2004
11. Sep 27, 2004

### maverick280857

Hi

I don't know if this is going to help, but if you write (2n)!/[(n!)(n+1)!] as ((2n)!/[n!]^2)*(n!/(n+1)!) then you have to prove that 2nCn is divisible by (n+1) for all n >= 0.

TeXifying it....

$$\frac{(2n)!}{n!(n+1)!} = \frac{(2n)!}{(n!)^{2}} \frac{n!}{(n+1)!} = \frac{^{2n}C_{n}}{n+1}$$

I'm sorry if I restated somebody else's suggestion/solution (I haven't had the time to read each and every post in this thread).

Cheers
Vivek

Last edited: Sep 27, 2004
12. Sep 28, 2004

### phoenixthoth

Algebraically prove the identity B(n+1,k)=B(n,k)+B(n,k-1) and then use induction.

13. Sep 28, 2004

### TenaliRaman

i really don't understand the problem,
i think robert has already given two proofs to the problem ...

as to proving binomial coefficients as natural,
in (1+x)^n,
the coefficients C(n,r) represent the number of ways i can choose 'r' (1+x)'s out of the 'n' (1+x)'s since they would be contributing to the term x^i ... since this is a counting argument , the value must be a natural value.

-- AI

14. Oct 2, 2004

### robert Ihnot

We can also show a theorem: N! divides the product of any n successive integers (wthout remainer). This then shows that (n+a)!/a! is also divisible by n!. I refer to Gokul43201 number theory problem dealing with the zeros of 1994!

The number of times that p, a prime, divides n! is: $$\sum_{i>0} [\frac{n}{p^i}]$$ where the parenthesis represent the greatest integer in n divided by p^i.
$$\sum_{i>0}[\frac{n+a}{p}]$$ greater than or equal to:$$\sum_{i>0}[\frac{n}{p}]+\sum_{i>0}[\frac{a}{p}]$$ for all p.