# Asymptotics for sums involving factorials

This question is rather general, but I have recently encountered the following situation in a variety of different settings.

Let us suppose that we are given a complicated sum involving factorials and some other "less problematic stuff". For example, $$\sum_{k=1}^n \frac{(3k)! \, n! \, n!}{k! \, (k-4)!} 3^{n-4k}$$ (This is just an example - it is possible that this sum may be solved by some ad hoc methods, but this is not the point of the question.)

My question is, in general, how to derive asymptotic estimates of such sums. For me, the most obvious idea is to replace the factorials by their Stirling approximation and then to simplify the resulting expression in order to obtain a single series in the summand.

But here comes the problem: the Stirling's approximation is not convergent and thus cannot be (at least as to my poor knowledge) summed term-by-term. So my question is: is there any sufficiently general method to overcome this problem? For instance some trick with the Stirling approximation, or some other approximation of factorial that is more useful.

Sums like this, where each term is at least as large as the sum of the previous terms, can be handled by simply dividing out the largest term of the sum. So if we call

$$S_n = \sum_{k=4}^{n} \frac{(3k)!}{3^{4k} k! (k-4)!}$$

then we would like to study

\begin{align} T_n &= \frac{3^{4n} n! (n-4)!}{(3n)!} S_n \\ &= 1 + \frac{3^4 n (n-4)}{3n(3n-1)(3n-2)} + \frac{3^8 n (n-1) (n-4)(n-5)}{3n(3n-1)(3n-2)(3n-3)(3n-4)(3n-5)} + \cdots \\ &= \sum_{k=0}^{n-4} \frac{3^{4k} \prod_{j=0}^{k-1} (n-j)(n-j-4)}{\prod_{j=0}^{k-1} (3n-3j)(3n-3j-1)(3n-3j-2)}. \end{align}

If we cut the sum off after the $N^\text{th}$ term we omit $n-N-3$ terms, each of which is less than

$$\frac{3^{4N} \prod_{j=0}^{N-1} (n-j)(n-j-4)}{\prod_{j=0}^{N-1} (3n-3j)(3n-3j-1)(3n-3j-2)},$$

and so obtain an error of $O(n^{-(N-1)})$. But the $N^\text{th}$ term is also $O(n^{-(N-1)})$, so that

$$T_n = \sum_{k=0}^{N-2} \frac{3^{4k} \prod_{j=0}^{k-1} (n-j)(n-j-4)}{\prod_{j=0}^{k-1} (3n-3j)(3n-3j-1)(3n-3j-2)} + O\left(n^{-(N-1)}\right)$$

as $n \to \infty$, giving us a full asymptotic series for $T_n$. In other words,

$$T_n \approx \sum_{k=0}^{\infty} \frac{3^{4k} \prod_{j=0}^{k-1} (n-j)(n-j-4)}{\prod_{j=0}^{k-1} (3n-3j)(3n-3j-1)(3n-3j-2)}$$

as $n \to \infty$. Of course this series is pretty ugly, but it does imply the existence of an asymptotic series of the form

$$T_n \approx \sum_{k=0}^{\infty} \frac{a_k}{n^k}.$$

We can use the first series to calculate as many terms of this new one as we want. For instance,

$$T_n = 1+\frac{3}{n}-\frac{83}{3 n^3}-\frac{413}{3 n^4}-\frac{13190}{27 n^5}-\frac{39217}{27 n^6}-\frac{863603}{243 n^7}-\frac{402734}{81 n^8} + O\left(\frac{1}{n^9}\right).$$

In some special cases the coefficients $a_k$ can be calculated explicitly, but this can involve some work. You may wish to read Section 3.3 in de Bruijn's Asymptotic Methods in Analysis.