Asymptotic Expansions of a Recurrence Relation

In today’s post, I investigate a simple recurrence relation and show how it is possible to describe its behaviour asymptotically at large times. The relation describing how the series evolves at a time n will depend both on its value at the earlier time n/2 and on whether n is even or odd, which, as we will see, introduces a `period doubling’ behaviour in the asymptotics. The proof will involve defining a Dirichlet generating function for the series, showing that it satisfies a functional equation and has a meromorphic extension to the whole complex plane, and then inverting the generating function with Perron’s formula. Cauchy’s residue theorem relates the terms of the asymptotic expansion to the poles of the meromorphic extension of the Dirichlet series. Such an approach is well-known in analytic number theory, originally used by Riemann to give the explicit formula for the prime counting function in terms of the zeros of the Riemann zeta function. However, Dirichlet generating functions can be applied in many other situations to generate asymptotic expansions (see the references for examples). Although I will concentrate on a specific difference equation here, the techniques described are quite general and also apply to many other kinds of series.

This post grew out of an answer I gave to a question by Byron Schmuland at the math.stackexchange website. Continue reading “Asymptotic Expansions of a Recurrence Relation”