# Going from a recursion formula to a recursion formula involving the logs only

I want to compute the terms $a_n$ from some recursion formula of the form:

$a_n=\sum_{k=1}^nb_ka_{n-k}$ with some initial condition $a_0$, and the $b_k$ are known. Also, let's assume there is no closed form for $a_n$.

These terms grow very rapidly. Therefore I thought using a recursion formula involving the logs might be more tractable. However, I don't know if it is possible to go from this recursion formula involving $a_n$ and $b_n$ to another one involving $\log(a_n)$ and $\log(b_n)$ only. At first it seemed obvious to me, but I am somewhat doubting now.

The main problem I encounter there is that I get the log of a sum on the right-hand side, that I would like to express as a sum of the logs instead. Maybe some kind of good approximation is possible ?

Some context : this problem occurs in a physics problem, when computing recursively some partition function. I want to avoid overflow issues.

EDIT : adding some information:

If it is of any help, $b_k=(\frac{1}{1-e^{-k\beta}})^3$ where $\beta$ can be close to $0$ (so $b_k$ can possibly take very high values). The initial condition is $a_0=1$.

• If $f_b(x)=\sum_{n\geq 0}b_n x^n$ and $f_a(x)=\sum_{n\geq 0}a_n x^n$, the recursion gives $a_n = -b_0 a_n + [x^n]f_a(x)f_b(x)$, so $f_a(x)$ is the solution of simple differential equation and the order of growth of $a_n$ can be estimated with various techniques. – Jack D'Aurizio Oct 20 '16 at 21:16
• However, a precise answer requires a bit more knowledge on the $\{a_n\}_{n\geq 0}$ and $\{b_n\}_{n\geq 0}$ sequences. What do you actually know about them? – Jack D'Aurizio Oct 20 '16 at 21:17
• @JackD'Aurizio Thanks for your input. I added some information at the bottom. I guess I could approximate $b_k$ for small $\beta$ (even if I'd rather not to... just to be sure of the relevance of my results) – Evariste Oct 20 '16 at 21:23

If $a_n =\sum_{k=1}^nb_ka_{n-k}$, let $A(x) =\sum_{n=0}^{\infty} a_n x^n$ and $B(x) =\sum_{n=0}^{\infty} b_n x^n$.

Then, in the usual manner,

$\begin{array}\\ A(x)B(x) &=\sum_{i=0}^{\infty} a_i x^i\sum_{j=0}^{\infty} b_j x^j\\ &=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty} a_i b_j x^{i+j}\\ &=\sum_{n=0}^{\infty}\sum_{i=0}^{n} a_i b_{n-i} x^{n}\\ &=\sum_{n=0}^{\infty}x^n\sum_{i=0}^{n} a_{n-i} b_{i} \\ &=\sum_{n=0}^{\infty}x^n\sum_{i=0}^{n} a_{n-i} b_{i} \\ &=a_0b_0+\sum_{n=1}^{\infty}x^n\left(a_nb_0+\sum_{i=1}^{n} a_{n-i} b_{i}\right)\\ &=a_0b_0+\sum_{n=1}^{\infty}x^na_nb_0+\sum_{n=1}^{\infty}x^n\sum_{i=1}^{n} a_{n-i} b_{i}\\ &=a_0b_0+b_0\sum_{n=1}^{\infty}x^na_n+\sum_{n=1}^{\infty}x^n\sum_{i=1}^{n} a_{n-i} b_{i}\\ &=a_0b_0+b_0(A(x)-a_0)+\sum_{n=1}^{\infty}x^n a_{n}\\ &=a_0b_0+b_0(A(x)-a_0)+(A(x)-a_0)\\ &=A(x)-a_0\\ \text{so}\\ a_0 &=A(x)-A(x)B(x)\\ &=A(x)(1-B(x))\\ \text{or}\\ A(x) &=\dfrac{1}{1-B(x)}\\ \end{array}$

If you can write $1-B(x) =\prod_{k=1}^m (c_k-x)$, you can get an estimate for the growth of the $a_n$ in terms of the largest of the $(1/c_k)^n$.

If $B(x)$ is a power series rather than a polynomial, it is harder.

• In the current framework, it is reasonable to approximate $B(x)$ with $\frac{1}{1-x}+(b_1-1)x$. In such a case, the magnitude of $a_n$ (or $\log a_n$) is easy to compute and just depends on $b_1$. – Jack D'Aurizio Oct 20 '16 at 22:09
• @JackD'Aurizio This would be achieved by comparing the series expansion at $x=0$ of the RHS right ? Or at b=+inf ? – Evariste Oct 21 '16 at 4:30
• @Evariste: it is a bit of both. If we approximate $B(x)$ in such a way, it is reasonable to expect that the closest zero to the origin of $B(x)-1$ is not changed by much, so neither it is the behaviour of $a_n$ that follows from $$A(x)=\frac{1}{1-B(x)}$$ – Jack D'Aurizio Oct 21 '16 at 5:01
• @JackD'aurizio I don't get how I can infer the behaviour of a single $a_n$ from that of the sum... The first term of the series expansion seems to be $-\frac {1}{b_1x}$. And now what ? I can't derive n times and evaluate at $0$ since it diverges – Evariste Oct 21 '16 at 10:43
• @Evariste: study the case $$A(x)=\sum_{n\geq 0}a_n x^n = \frac{1}{1-\frac{1}{1-x}-cx}$$ through partial fraction decomposition. Then approximate $1-B(x)$ with $1-\frac{1}{1-x}-cx$. That was my suggestion. – Jack D'Aurizio Oct 21 '16 at 10:45