Divide-and-conquer recurrences -- classification of asymptotics (Q1592813)

This paper investigates the asymptotic behaviour of the sequence \(\{f_n\}\) defined by means of a divide-and-conquer recursion \[ [2^n-(a_1+a_0)]f_n=a_1\sum_{k=0}^{n-1}\binom{n}{k}\alpha^{n- k}f_k+b_1\beta^n,\quad n>l , \tag{1} \] where \(\alpha ,\beta >0, a_0,a_1\neq 0,b_1\in\mathbb R\) are given parameters and \(f_0,f_1,\dots ,f_l\) are the initial values. It is known that some particular cases of this recurrence relation admit a very different asymptotic behaviour of solutions. The main result of this paper gives a complete list of all possible types of the asymptotic behaviour of general recurrences defined by use of (1). The sign of \(\triangle =2\alpha -\beta\) turns out to be the key assumption of this statement. Put \(\rho =\log_2a_1\). If \(\triangle >0\), then \[ \alpha^{-n}f_n=n^{\rho}K(\log _2n)+O(n^{\rho -1}) , \tag{2} \] where \(K\) is an analytic and periodic function with period 1. If \(\triangle <0\), then \[ \left (\frac{\beta}{2}\right)^{-n}f_n=b_1+O(n^{-1}) . \] If \(\triangle =0\), then some additional requirements on the value of \(\rho\) are necessary to prove the modifications of formula (2). The method of the proof is based on considering the exponential generating function \(f(z)\) of the sequence \(\{f_n\}\) given by \[ f(z)=\sum_{n=0}^{\infty}\frac{f_n}{n!}z^n . \] It is shown that \(f(z)\) is an entire solution of the functional equation \[ f(2z)=(a_1\text{ e}^{\alpha z}+a_0)f(z)+b_1\text{ e}^{\beta z}+b_0(z) \] and its asymptotic behaviour determines the asymptotics of \(f_n\).