1

I am considering the following system of recurrence of relations: for $i=1,2,\dots,n-1$, \begin{align*} &a_i=\frac{2}{3(n-i)+2}b_i+\frac{3(n-i)}{3(n-i)+2}a_{i+1}\\ &b_i=\frac{i}{n\left[3(n-i)+1\right]}+\frac{3(n-i)}{\left[3(n-i)+1\right](i+1)}a_{i+1}+\frac{3i(n-i)}{\left[3(n-i)+1\right](i+1)}b_{i+1}, \end{align*} with $a_n=b_n=1$.

Is there any general methodology that can deal with this kind of recurrence relations?

At first, I solved another recurrence relations in which the second one is much simpler: \begin{align*} &a'_i=\frac{2}{3(n-i)+2}b'_i+\frac{3(n-i)}{3(n-i)+2}a'_{i+1}\\ &b'_i=\frac{i}{n\left[3(n-i)+1\right]}+\frac{3(n-i)}{3(n-i)+1}b'_{i+1}, \end{align*} with $a'_n=b'_n=1$. Using these relations a few times (from $n$ backward), I am able to observe that $a'_i=\frac{9n+i}{10n}$ and $b'_i=\frac{3n+i}{4n}$. However, I then realize that I should study $a_i$ and $b_i$ instead of $a'_i$ and $b'_i$. But I don't know how to get the exact solutions.

Please give me some help or hints. Thanks a lot.

user377704
  • 421

1 Answers1

0

You could use generating functions. Define $A(z) = \sum_{i \ge 0} a_a z^i$, $B(z) = \sum_{i \ge 0} b_i z^i$. Multiply out (to get rid of fractions), multiply the recurrences by $z^i$ and sum over $i \ge 0$:

$\begin{align*} (3 n + 2) \sum_{i \ge 0} a_i z^i - 3 \sum_{i \ge 0} i a_i z^i &= 2 \sum_{i \ge 0} b_i z^i + 3 n \sum_{i \ge 0} a_{i + 1} z^i - 3 \sum_{i \ge 0} i a_{i + 1} z^i \end{align*}$

Now recognize some sums, i.e. $\sum_{i \ge 0} i a_i z^i = z \frac{d}{d z} A(z)$ and $\sum_{i \ge 0} a_{i + 1} z^i = \frac{A(z) - a_0}{z}$. This gives a system of linear differential equations that you can (hopefully) solve.

vonbrand
  • 27,812