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

an=∑nk=1bkan−ka_n=\sum_{k=1}^nb_ka_{n-k} with some initial condition a0a_0, and the bkb_k are known.

Also, let’s assume there is no closed form for ana_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 ana_n and bnb_n to another one involving log(an)\log(a_n) and log(bn)\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, bk=(11−e−kβ)3b_k=(\frac{1}{1-e^{-k\beta}})^3 where β\beta can be close to 00 (so bkb_k can possibly take very high values). The initial condition is a0=1a_0=1.

=================

If fb(x)=∑n≥0bnxnf_b(x)=\sum_{n\geq 0}b_n x^n and fa(x)=∑n≥0anxnf_a(x)=\sum_{n\geq 0}a_n x^n, the recursion gives an=−b0an+[xn]fa(x)fb(x)a_n = -b_0 a_n + [x^n]f_a(x)f_b(x), so fa(x)f_a(x) is the solution of simple differential equation and the order of growth of ana_n can be estimated with various techniques.

– Jack D’Aurizio

Oct 20 at 21:16

However, a precise answer requires a bit more knowledge on the {an}n≥0\{a_n\}_{n\geq 0} and {bn}n≥0\{b_n\}_{n\geq 0} sequences. What do you actually know about them?

– Jack D’Aurizio

Oct 20 at 21:17

@JackD’Aurizio Thanks for your input. I added some information at the bottom. I guess I could approximate bkb_k for small β\beta (even if I’d rather not to… just to be sure of the relevance of my results)

– Evariste

Oct 20 at 21:23

=================

1 Answer

1

=================

If

an=∑nk=1bkan−ka_n

=\sum_{k=1}^nb_ka_{n-k}

,

let

A(x)=∑∞n=0anxnA(x)

=\sum_{n=0}^{\infty} a_n x^n

and

B(x)=∑∞n=0bnxnB(x)

=\sum_{n=0}^{\infty} b_n x^n

.

Then,

in the usual manner,

A(x)B(x)=∑∞i=0aixi∑∞j=0bjxj=∑∞i=0∑∞j=0aibjxi+j=∑∞n=0∑ni=0aibn−ixn=∑∞n=0xn∑ni=0an−ibi=∑∞n=0xn∑ni=0an−ibi=a0b0+∑∞n=1xn(anb0+∑ni=1an−ibi)=a0b0+∑∞n=1xnanb0+∑∞n=1xn∑ni=1an−ibi=a0b0+b0∑∞n=1xnan+∑∞n=1xn∑ni=1an−ibi=a0b0+b0(A(x)−a0)+∑∞n=1xnan=a0b0+b0(A(x)−a0)+(A(x)−a0)=A(x)−a0soa0=A(x)−A(x)B(x)=A(x)(1−B(x))orA(x)=11−B(x)\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)=∏mk=1(ck−x)1-B(x)

=\prod_{k=1}^m (c_k-x)

,

you can get an estimate

for the growth of

the ana_n

in terms of

the largest of the

(1/ck)n(1/c_k)^n.

If B(x)B(x) is a power series

rather than a polynomial,

it is harder.

In the current framework, it is reasonable to approximate B(x)B(x) with 11−x+(b1−1)x\frac{1}{1-x}+(b_1-1)x. In such a case, the magnitude of ana_n (or logan\log a_n) is easy to compute and just depends on b1b_1.

– Jack D’Aurizio

Oct 20 at 22:09

@JackD’Aurizio This would be achieved by comparing the series expansion at x=0x=0 of the RHS right ? Or at b=+inf ?

– Evariste

2 days ago

@Evariste: it is a bit of both. If we approximate B(x)B(x) in such a way, it is reasonable to expect that the closest zero to the origin of B(x)−1B(x)-1 is not changed by much, so neither it is the behaviour of ana_n that follows from A(x)=11−B(x)A(x)=\frac{1}{1-B(x)}

– Jack D’Aurizio

2 days ago

@JackD’aurizio I don’t get how I can infer the behaviour of a single an a_n from that of the sum… The first term of the series expansion seems to be −1b1x-\frac {1}{b_1x}. And now what ? I can’t derive n times and evaluate at 00 since it diverges

– Evariste

2 days ago

@Evariste: study the case A(x)=∑n≥0anxn=11−11−x−cx 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)1-B(x) with 1−11−x−cx1-\frac{1}{1-x}-cx. That was my suggestion.

– Jack D’Aurizio

2 days ago