Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 26, 2004 #1


    User Avatar

    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? :confused:

    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?

  2. jcsd
  3. Sep 26, 2004 #2
    Let B(n,k) be the usual binomial coefficient: n!/[k!(n-k)!].



    Last edited: Sep 26, 2004
  4. Sep 26, 2004 #3
    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/~history/Miscellaneous/CatalanNumbers/catalan.html
    Last edited: Sep 26, 2004
  5. Sep 26, 2004 #4


    User Avatar

    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:
    So we get, for f(n):
    Which is B(2n, n-1)/n

    I think :confused:

    Robert thank you for the information, I'll try to google a proof.
    Last edited: Sep 26, 2004
  6. Sep 26, 2004 #5
    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 [Broken]
    Last edited by a moderator: May 1, 2017
  7. Sep 26, 2004 #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.
    Last edited: Sep 26, 2004
  8. Sep 26, 2004 #7


    User Avatar

    This also looks wrong to me, but it's too late now, I'll look more closely tomorrow.
  9. Sep 26, 2004 #8
    It is indeed wrong, 2(k+1)!/((k+1)!(k+2)!) = 2(k+1)k!/((k+1)k!(k+2)(k+1)!).
  10. Sep 27, 2004 #9
    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!
  11. Sep 27, 2004 #10


    User Avatar

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

    (a over b means the binominal coefficient)

    = (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 :confused: Anyone? I have a feeling this could even be a "textbook proof"... And google refuses to give me anything useful these days :frown:
    Last edited: Sep 27, 2004
  12. Sep 27, 2004 #11

    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}[/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).

    Last edited: Sep 27, 2004
  13. Sep 28, 2004 #12
    Algebraically prove the identity B(n+1,k)=B(n,k)+B(n,k-1) and then use induction.
  14. Sep 28, 2004 #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
  15. Oct 2, 2004 #14
    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: [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.
    Last edited: Oct 3, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook