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

pig

I tried induction, but got no results. What I get is:

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.

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.

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 [tex]\frac{4!}{2!3!}=2[/tex]

See: http://www-gap.dcs.st-and.ac.uk/~his...s/catalan.html

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.

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/depar...eth/intro.html

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.

pig

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

Muzza

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

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!

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

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

[tex]
\frac{(2n)!}{n!(n+1)!} = \frac{(2n)!}{(n!)^{2}} \frac{n!}{(n+1)!} = \frac{^{2n}C_{n}}{n+1}[/tex]

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

phoenixthoth

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

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

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!

:http://www.physicsforums.com/showthread.php?t=35582

The number of times that p, a prime, divides n! is: [tex]\sum_{i>0} [\frac{n}{p^i}][/tex] where the parenthesis represent the greatest integer in n divided by p^i.

Skipping a little ahead because of the latex, the inequality we want is:

[tex]\sum_{i>0}[\frac{n+a}{p}][/tex] greater than or equal to:[tex]\sum_{i>0}[\frac{n}{p}]+\sum_{i>0}[\frac{a}{p}][/tex] for all p.

This comes about because let n=kp+r for r less than p and positive or zero, and let a=jp+y, y same conditions as above, then greatest integer in n+a =k+j + greatest integer in (r+y)/p which is greater than or equal to k+J.