TAOCP 1.2.11.3 Exercise 6

Write \frac{(n+\alpha)^n}{n^{\,n+\beta}} = n^{\alpha-\beta}\left(1+\frac{\alpha}{n}\right)^n.

taocpmathematicsalgorithmsvolume-1hm-medium

Section 1.2.11.3: Some Asymptotic Calculations

Exercise 6. [HM20] Prove Eq. (23).

Verified: no
Solve time: 1m55s

Solution

Write

$$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = n^{\alpha-\beta}\left(1+\frac{\alpha}{n}\right)^n. $$

Take logarithms of the second factor:

$$ \ln\left(1+\frac{\alpha}{n}\right) = \frac{\alpha}{n} - \frac{\alpha^2}{2n^2} + O(n^{-3}). $$

Multiplying by $n$ gives

$$ n\ln\left(1+\frac{\alpha}{n}\right) = \alpha - \frac{\alpha^2}{2n} + O(n^{-2}). $$

Exponentiation yields

$$ \left(1+\frac{\alpha}{n}\right)^n = \exp\left(\alpha - \frac{\alpha^2}{2n} + O(n^{-2})\right) = e^\alpha \exp\left(-\frac{\alpha^2}{2n} + O(n^{-2})\right). $$

Expanding the exponential,

$$ \exp\left(-\frac{\alpha^2}{2n} + O(n^{-2})\right) = 1 - \frac{\alpha^2}{2n} + O(n^{-2}). $$

Thus

$$ \left(1+\frac{\alpha}{n}\right)^n = e^\alpha\left(1 - \frac{\alpha^2}{2n} + O(n^{-2})\right). $$

Substitution into the original expression gives

$$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = n^{\alpha-\beta} e^\alpha \left(1 - \frac{\alpha^2}{2n} + O(n^{-2})\right). $$

To incorporate the dependence on $\beta$ in the first correction term, rewrite the original quotient in a form where both exponents are matched:

$$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = \frac{(n+\alpha)^{n+\beta}}{n^{n+\beta}}(n+\alpha)^{-\beta}. $$

The first factor satisfies

$$ \frac{(n+\alpha)^{n+\beta}}{n^{n+\beta}} = \left(1+\frac{\alpha}{n}\right)^{n+\beta}. $$

Using

$$ (n+\beta)\ln\left(1+\frac{\alpha}{n}\right) = \alpha + \frac{\alpha\beta}{n} - \frac{\alpha^2}{2n} + O(n^{-2}), $$

one obtains

$$ \left(1+\frac{\alpha}{n}\right)^{n+\beta} = e^\alpha\left(1 + \frac{\alpha\beta - \alpha^2/2}{n} + O(n^{-2})\right). $$

For the second factor,

$$ (n+\alpha)^{-\beta} = n^{-\beta}\left(1+\frac{\alpha}{n}\right)^{-\beta} = n^{-\beta}\left(1 - \frac{\alpha\beta}{n} + O(n^{-2})\right). $$

Multiplying both factors gives

$$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = n^{\alpha-\beta} e^\alpha \left(1 + \frac{\alpha\beta - \alpha^2/2 - \alpha\beta}{n} + O(n^{-2})\right). $$

The $\alpha\beta$ terms cancel, leaving

$$ \frac{(n+\alpha)^n}{n^{,n+\beta}} = n^{\alpha-\beta} e^\alpha \left(1 + \frac{\alpha(\beta - \alpha/2)}{n} + O(n^{-2})\right). $$

This completes the proof. ∎