1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove: (n + d)! / n! = (n + d/2)^(d)

  1. Apr 10, 2016 #1
    1. The problem statement, all variables and given/known data

    Prove: (n + d)! / n! ≅ (n + d/2)^(d)

    where: n >> d >> 1

    2. Relevant equations


    3. The attempt at a solution

    (n + d)! / n! = (n + 1) * (n + 2) * . . . (n + d)

    Ln [ (n + d)! / n! ] = Ln [ (n + 1) * (n + 2) * . . . (n + d) ]

    Ln [ (n + d)! / n! ] = Ln (n + 1) + Ln (n + 2) + . . . Ln (n + d) ]

    Ln [ (n + d)! / n! ] = Σ Ln (n + i) , from i = 1 to d

    if d >> 1, then

    [ Σ Ln (n + i) , from i = 1 to d ] ≅ ∫ Ln (x) dx , from x = (n + 1) to (n + d)

    [ Σ Ln (n + i) , from i = 1 to d ] ≅ x * Ln (x) - x , from x = (n + 1) to (n + d)

    [ Σ Ln (n + i) , from i = 1 to d ] ≅ [ (n + d) * Ln ((n + d)) - (n + d) ] - [ (n + 1) * Ln (n + 1) - (n + 1) ]

    [ Σ Ln (n + i) , from i = 1 to d ] ≅ (n + d) * Ln (n + d) - (n + 1) * Ln (n + 1) - d + 1

    = ?


    NOTE:

    I'm trying to prove an equation that was simply "given" in a Physical Chemistry textbook. I don't think that textbook intended for its students to solve that equation's proof as a "homework" exercise. Since my "Problem Statement" was simply "given", and not specifically stated as a "homework" exercise, I'm not certain I'm even using the correct approach to solving my "Problem Statement". Maybe instead of converting to Ln () and then attempting to integrate, the "Problem Statement" can be solved algebraically more easily?
     
    Last edited: Apr 10, 2016
  2. jcsd
  3. Apr 10, 2016 #2

    Charles Link

    User Avatar
    Homework Helper

    Suggest using Stirling's formula : ## ln(N!)=N ln(N) -N ## for large N. One additional hint is when you expand ## ln(1+d/n) ## in a Taylor series, you need to go to the second power in d/n for one of the terms.
     
    Last edited: Apr 10, 2016
  4. Apr 10, 2016 #3
    Thanks for the reply; however, I believe that is what I essentially did during the following steps stated in my original post:

    As stated in my original post, once I evaluate that "Stirling Equation" from x ≅ (n + 1) to (n + d), I don't know how to further simply that equation to the final simplified equation given in the original problem statement.
     
    Last edited: Apr 10, 2016
  5. Apr 10, 2016 #4

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    If you take the log of [itex](n+\frac{d}{2})^d[/itex] you get:

    [itex]d ln(n + \frac{d}{2}) = d ln(n (1+\frac{d}{2n})) = d ln(n) + d ln(1+\frac{d}{2n})[/itex]

    At this point, you can use the approximation: [itex]ln(1+x) \approx x[/itex] when [itex]x \ll 1[/itex]. So you get:
    [itex](n+\frac{d}{2})^d \approx d ln(n) + \frac{d^2}{2n}[/itex]

    Then you can also write: [itex]ln(n \cdot (n+1) \cdot (n+2) ... \cdot (n+d)) = ln(n^d \cdot(1+\frac{1}{n}) \cdot(1+ \frac{2}{n}) ... \cdot(1+\frac{d}{n}))[/itex]

    Using the fact that [itex]ln(x \cdot y) = ln(x) + ln(y)[/itex], this can be written as:

    [itex]d ln(n) + ln(1+\frac{1}{n}) + ... + ln(1+\frac{d}{n})[/itex]

    Now, use the approximation [itex]ln(1+x) \approx x[/itex] for each term in the sum.
     
  6. Apr 10, 2016 #5
    Thanks

    Using the approximation you recommended, I was able to continue where you left off, as follows:

    [itex]d ln(n) + ln(1+\frac{1}{n}) + ... + ln(1+\frac{d}{n})[/itex]

    [itex]d ln(n) + \frac{1}{n} + \frac{2}{n} + ... \frac{d}{n}[/itex]

    [itex]d ln(n) + \frac{1}{n} \cdot (1 + 2 + ... d)[/itex]

    [itex]d ln(n) + \frac{1}{n} \cdot \sum_{i=1}^d i[/itex]

    if d >> 1

    [itex]d ln(n) + \frac{1}{n} \cdot \int_1^d i \, dx[/itex]

    [itex]d ln(n) + \frac{1}{n} \cdot \left. \frac{1}{2}i^2 \right|_1^d[/itex]

    [itex]d ln(n) + \frac{1}{n} \cdot \frac{1}{2}(d^2 - 1) [/itex]

    [itex]d ln(n) + \frac{d^2}{2n} [/itex]


    Which is the same equation as I converted to red text in your above referenced post, therefore the original Problem Statement has been verified.

    However, although the original Problem Statement has been verified, we verified it by "working from both ends of the equations", and verifying "both ends of the equations meet (are the same) in the middle". I'm not totally satisfied with this "proof" technique because I'd rather learn/think of a method that starts from the left side of the Problem Statement and continually simplify it until it results in the final equation (instead of deriving from both ends, and verifying the derivations are equal in the "middle")

    Next I will try the Taylor Expansion hint Charles posted above, to see if that will result in a continuous type of proof I'm looking for.
     
    Last edited: Apr 10, 2016
  7. Apr 10, 2016 #6

    Charles Link

    User Avatar
    Homework Helper

    I think you might still need to work both sides of the equation using the Stirling's formula (which you essentially derived.) You basically wind up solving both sides to order (d/n)^2 and showing the terms agree.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove: (n + d)! / n! = (n + d/2)^(d)
Loading...