Thread Closed

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

 
Share Thread Thread Tools
Sep26-04, 01:22 PM   #1
pig
 

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


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.
 
PhysOrg.com
PhysOrg
mathematics news on PhysOrg.com

>> Mathematicians analyze social divisions using cell phone data
>> Can math models of gaming strategies be used to detect terrorism networks?
>> Mathematician proves there are infinitely many pairs of prime numbers less than 70 million units apart
Sep26-04, 06:40 PM   #2
 
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.
 
Sep26-04, 07:30 PM   #3
 
Recognitions:
Gold Membership Gold Member
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
 
Sep26-04, 07:57 PM   #4
pig
 

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


Quote by 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.
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.
 
Sep26-04, 08:32 PM   #5
 
Recognitions:
Gold Membership Gold Member
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
 
Sep26-04, 08:58 PM   #6
 
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.
 
Sep26-04, 09:50 PM   #7
pig
 
This also looks wrong to me, but it's too late now, I'll look more closely tomorrow.
 
Sep26-04, 11:39 PM   #8
 
It is indeed wrong, 2(k+1)!/((k+1)!(k+2)!) = 2(k+1)k!/((k+1)k!(k+2)(k+1)!).
 
Sep27-04, 02:17 AM   #9
 
Quote by Muzza
It is indeed wrong, 2(k+1)!/((k+1)!(k+2)!) = 2(k+1)k!/((k+1)k!(k+2)(k+1)!).
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!
 
Sep27-04, 10:09 AM   #10
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
 
Sep27-04, 10:59 AM   #11
 
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
 
Sep28-04, 11:50 AM   #12
 
Quote by 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
Algebraically prove the identity B(n+1,k)=B(n,k)+B(n,k-1) and then use induction.
 
Sep28-04, 01:58 PM   #13
 
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
 
Oct2-04, 08:33 PM   #14
 
Recognitions:
Gold Membership Gold Member
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.
 
Thread Closed
Thread Tools


Similar Threads for: Proof that (2n)!/[n!(n+1)!] is natural for natural n
Thread Forum Replies
Is this natural? Academic Guidance 0
Proof w/ natural log and Riemann Sum Calculus & Beyond Homework 3
Natural Law General Discussion 7
All Natural? General Discussion 13
Natural God General Discussion 3