0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Oct 20 '16 at 21:16
  • $\begingroup$ 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? $\endgroup$ – Jack D'Aurizio Oct 20 '16 at 21:17
  • $\begingroup$ @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) $\endgroup$ – Evariste Oct 20 '16 at 21:23
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Oct 20 '16 at 22:09
  • $\begingroup$ @JackD'Aurizio This would be achieved by comparing the series expansion at $x=0$ of the RHS right ? Or at b=+inf ? $\endgroup$ – Evariste Oct 21 '16 at 4:30
  • $\begingroup$ @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)}$$ $\endgroup$ – Jack D'Aurizio Oct 21 '16 at 5:01
  • $\begingroup$ @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 $\endgroup$ – Evariste Oct 21 '16 at 10:43
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Oct 21 '16 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.