Tools For Analyzing A Recursive Relationship

Question

I am working with a recursively defined sequence and don't know what tools are out there to understand the limit of the ratio of it's successive terms (which I have a hunch is finite). Here is the sequence:

For $a_1=1$, $b_1=-4$:

$$a_n=-\frac{(2n+3)}{(2n-2)}\sum_{k=1}^{n-1}a_kb_{n-k}$$

$$b_n=-\frac{(2n+2)}{(2n-1)}a_n-\frac{(n+1)}{(2n-1)}\sum_{k=1}^{n-1}b_kb_{n-k}$$

And I would like to know $\lim_{n\to\infty}\frac{a_{n+1}}{a_n}$ or equivalently $\lim_{n\to\infty}\frac{b_{n+1}}{b_n}$. Is there a way to get this in an explicit form? Or a way to find bounds?

Answer 1

I have no idea how to do it analytically, but numerically in Mathematica I would do this:

nlist = {100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000,
         3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 20000,
         30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000};
{mmax, nmax} = {Length[nlist], Last[nlist]};

a = ConstantArray[0, nmax];
b = ConstantArray[0, nmax];
c = ConstantArray[0, mmax];
{a[[1]], b[[1]]} = {1., -4.};
{m, t} = {1, SessionTime[]};

Monitor[
 Do[va = Take[a, n - 1]; vb = Take[b, n - 1]; s = {va, vb}.Reverse[vb];
    a[[n]] = (2 n + 3) s[[1]]/(2 - 2 n);
    b[[n]] = ((2 n + 3) s[[1]] - (n - 1) s[[2]]) (n + 1)/(n - 1)/(2 n - 1);
    If[n == nlist[[m]],
       c[[m]] = {n, SessionTime[]-t, a[[n]]/a[[n - 1]], b[[n]]/b[[n - 1]]};
       m = m + 1], {n, 2, nmax}],
 Row[{ProgressIndicator[n, {1, nmax}], n}, " "]]

TableForm[c, TableHeadings -> {None,
          {"n", "time(s)", "a[n]/a[n-1]", "b[n]/b[n-1]"}}]

from which a lot of information can be drawn, even if no demonstration.

Answer 2

Here's one idea, which was too long for a comment:

It's more convenient to start the sequence from $a_0 = 1$ and $b_0 = -4$, but we need to change our rational functions in $n$ to accommodate this change. We also clear out the fractions, and find our new recurrences:

$$ -(2n+2) a_{n+1} = (2n+7) \sum_{k=0}^n a_k b_{n-k} $$

$$ -(2n+3) b_{n+1} = (2n+6) a_{n+1} + (n+3) \sum_{k=0}^n b_k b_{n-k} $$

We want to pass to the generating functions for these series, since the sums on the right hand side look like cauchy products. So we set $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$. Standard manipulations (as can be found in chapter $1$ of the excellent, and freely available book generatingfunctionology) let us turn this recurrence into a family of differential equations (though you should double check my work in getting to this particular family):

$$ 2 A' + 7AB + 2x A' B + 2x A B' = 0 $$

$$ 4A + B + 3xB^2 + 2x A' + 2x B' + 2x^2 B B' = 0 $$

An analytic solution to these differential equations will give you lots of information about the asymptotics of your series $a_n$ and $b_n$ (again, you can read more in generatingfunctionology).

---

As an aside, since this is already a longer "comment" than I planned to leave, I'm not convinced the ratios $\frac{a_{n+1}}{a_n}$ or $\frac{b_{n+1}}{b_n}$ are bounded. I asked sage to compute the ratios, and while they stay below $25$ for all the values I calculated, they're increasing steadily. For instance, here is a plot of the ratios from $n=1450$ to $n=1500$. $\frac{a_{n+1}}{a_n}$ is shown in red, and $\frac{b_{n+1}}{b_n}$ is shown in blue:

Edit:

Since I had this data lying around, I computed the differences between the ratios. It looks like

$$ \frac{a_{n+1}}{a_n} - \frac{a_n}{a_{n-1}} \approx 35.9 n^{-1.99} $$

Here's a plot of this approximation against the actual differences, where I'm only taking every $20$th data point so the plot isn't too cluttered:

This does support the idea that $\frac{a_{n+1}}{a_n}$ should be bounded, since the differences are decaying almost quadratically quickly! So we would expect

$$ \frac{a_{N+1}}{a_N} = \frac{a_1}{a_0} + \sum_1^N \left ( \frac{a_{n+1}}{a_n} - \frac{a_n}{a_{n-1}} \right ) \lesssim \frac{a_1}{a_0} + \sum_1^N 35.9 n^{-1.99} \leq \frac{a_1}{a_0} + 35.9 \sum_1^\infty n^{-1.99} \approx \frac{a_1}{a_0} + 59.1 $$

---

I hope this helps ^_^