TAOCP 1.2.11.2 Exercise 8

Let m = an^2 + bn, \qquad a>0.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.11.2: Euler's Summation Formula

Exercise 8. [M23] Find the asymptotic value of $\ln((an^2+bn)!)$ with absolute error $O(n^{-2})$.

Verified: yes
Solve time: 45s

Solution

Let

$$ m = an^2 + bn, \qquad a>0. $$

By Stirling’s formula in logarithmic form,

$$ \ln(m!) = m\ln m - m + \frac{1}{2}\ln(2\pi m) + \frac{1}{12m} + O!\left(\frac{1}{m^3}\right). \tag{22} $$

Since $m = \Theta(n^2)$, the remainder term satisfies $O(1/m^3)=O(n^{-6})$, which is absorbed into the final required error $O(n^{-2})$.

Expansion of $\ln m$

Write

$$ m = an^2\left(1 + \frac{b}{an}\right). $$

Hence

$$ \ln m = \ln a + 2\ln n + \ln!\left(1 + \frac{b}{an}\right). $$

Let $x = \frac{b}{an}$. Then $x = O(n^{-1})$ and

$$ \ln(1+x) = x - \frac{x^2}{2} + O(x^3). $$

Thus

$$ \ln m = \ln a + 2\ln n + \frac{b}{an} - \frac{b^2}{2a^2n^2} + O(n^{-3}). \tag{23} $$

Expansion of $m\ln m$

Multiply (23) by $m = an^2 + bn$:

$$ m\ln m = (an^2 + bn)\left(\ln a + 2\ln n + \frac{b}{an} - \frac{b^2}{2a^2n^2} + O(n^{-3})\right). $$

Distribute terms.

From $(an^2 + bn)(\ln a + 2\ln n)$,

$$ an^2(\ln a + 2\ln n) + bn(\ln a + 2\ln n). $$

From $(an^2 + bn)\frac{b}{an}$,

$$ an^2\cdot \frac{b}{an} = bn, \qquad bn\cdot \frac{b}{an} = \frac{b^2}{a}. $$

From $(an^2 + bn)\left(-\frac{b^2}{2a^2n^2}\right)$,

$$ an^2\cdot \left(-\frac{b^2}{2a^2n^2}\right) = -\frac{b^2}{2a}, \qquad bn\cdot \left(-\frac{b^2}{2a^2n^2}\right) = -\frac{b^3}{2a^2n}. $$

The term $(an^2+bn)O(n^{-3})$ contributes $O(n^{-1})$.

Collecting terms,

$$ m\ln m = an^2(\ln a + 2\ln n)

  • bn(\ln a + 2\ln n + 1)
  • \frac{b^2}{2a}
  • \frac{b^3}{2a^2n}
  • O(n^{-1}). \tag{24} $$

Expansion of $-m$

$$ -m = -an^2 - bn. \tag{25} $$

Expansion of $\frac{1}{2}\ln(2\pi m)$

$$ \frac{1}{2}\ln(2\pi m) = \frac{1}{2}\ln(2\pi) + \frac{1}{2}\ln m. $$

Using (23),

$$ \frac{1}{2}\ln(2\pi m) = \frac{1}{2}\ln(2\pi a) + \ln n

  • \frac{b}{2an}
  • \frac{b^2}{4a^2n^2}
  • O(n^{-3}). \tag{26} $$

Expansion of $\frac{1}{12m}$

$$ \frac{1}{12m} = \frac{1}{12(an^2+bn)} = \frac{1}{12an^2}\cdot \frac{1}{1+\frac{b}{an}}. $$

Using $\frac{1}{1+x}=1-x+O(x^2)$,

$$ \frac{1}{12m} = \frac{1}{12an^2} + O(n^{-3}). \tag{27} $$

Combination

Add (24), (25), (26), and (27).

$n^2$-terms

$$ an^2(\ln a + 2\ln n) - an^2 = an^2(2\ln n + \ln a - 1). $$

$n$-terms

$$ bn(\ln a + 2\ln n + 1) - bn = bn(\ln a + 2\ln n). $$

Constant terms

$$ \frac{b^2}{2a} + \ln n + \frac{1}{2}\ln(2\pi a). $$

$n^{-1}$-terms

$$ -\frac{b^3}{2a^2n} + \frac{b}{2an} = \frac{1}{n}\left(\frac{b}{2a} - \frac{b^3}{2a^2}\right). $$

$n^{-2}$-terms

$$ \frac{1}{12an^2}. $$

All omitted contributions are $O(n^{-2})$.

Final result

$$ \ln\bigl((an^2+bn)!\bigr) = an^2(2\ln n + \ln a - 1)

  • bn(2\ln n + \ln a)
  • \ln n + \frac{1}{2}\ln(2\pi a)
  • \frac{b^2}{2a}
  • \frac{1}{n}\left(\frac{b}{2a} - \frac{b^3}{2a^2}\right)
  • \frac{1}{12an^2}
  • O(n^{-2}). $$

$$ \boxed{ \ln\bigl((an^2+bn)!\bigr) } $$