Finding a Closed Form for a Recurrence Relation

Question

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of rational functions to determine an exact formula. However, this only seems to work if your whole sequence depends only on the first few numbers in the sequence. But what if each term depends (linearly) on all the terms that come before it? For example:

Suppose we have a sequence $A_n$, such that we know $A_0$ and $A_n = \sum_{i=0}^{n-1}C_{i,n}A_i$ for $n \geq 1$ and some constants $C_{i,n}$. If we were to try the generating function idea we would get:

$$S = \sum_{n=0}^{\infty} A_nx^n = A_0 + \sum_{n=1}^{\infty}A_nx^n = A_0 + \sum_{n=1}^{\infty}\bigg(\sum_{i=0}^{n-1}C_{i,n}A_i\bigg)x^n$$

Normally, we would interchange the two sums, then get a function of $S$ as a rational function in $x$, and from there get the closed formula for $A_n$. However, we can not interchange the sum as the inner sum depends on the outer sum.

Can we still solve this problem with this technique and I just don't see how? Is there a different technique I can try? Any solution or reference would be greatly appreciated.

Edit: The $C_{i,n}$ depend on $n$ as well as $i$.

Answer 1

This is the approach towards what @EricTowers suggested. I have no idea how to proceed from here.

$$S = A_0 + \sum_{n=1}^{\infty}\left(\sum_{i=0}^{n-1}C_iA_i\right)x^n=A_0 + \sum_{i=0}^{\infty}\left(C_iA_i\right)\sum_{n=i+1}^{\infty}x^n......(1)$$

Because $$\sum_{n=i+1}^{\infty}x^n=x^{i+1}\sum_{j=0}^{\infty}x^j=\frac{x^{i+1}}{1-x}$$

So $$S =A_0 + \frac{x}{1-x}\sum_{i=0}^{\infty}C_iA_i x^{i}......(2)$$

Answer 2

Here is a specific example I encountered recently, though It does not solve the general case. Consider the recurrence where we are given $b_0$ and $$b_n = 3b_{n-1} + 2b_{n-2} + \cdots + 2b_0$$ for $n \geq 1$. So, we have $b_n = b_{n-1} + 2(b_{n-1} + \cdots + b_0)$. Let $f(z) = \sum_{n=0}^{\infty}b_n z^n$. Then $$\frac{2z}{1-z}f(z) = (2z + 2z^2 + \cdots)(b_0 + b_1z + \cdots)$$ and in this expression the coefficient of $z^n$ is $2b_{n-1} + \cdots + 2b_0$ for $n \geq 1$. Thus we get $$f(z) - b_0 = \left(\frac{2z}{1-z} + z\right)f(z)$$ recalling we need an extra $b_{n-1}$ in our coefficient of $z^n$. This then simplifies to $$f(x) = \frac{b_0(1-z)}{1-4z+z^2}$$ which can be solved by partial fraction to something of the form $$f(x) = \frac{A}{a-z} + \frac{B}{b-z} = \frac{A}{a(1-\frac{z}{a})} + \frac{B}{b(1-\frac{z}{b})}$$ and then we can use what we know about the geometric series.

This idea above will not solve your general problem $A_n = \sum_{i=0}^{n-1} C_{i,n}A_i$, but this idea can solve some such problems. The idea above depends on the $C_{i,n}$ to be somewhat "regular" and predictable. If the $C_{i,n}$ don't have a nice pattern like my example above I would not know what to do. Hopefully this is helpful.

Answer 3

Remember the product of series:

$$ \left( \sum_{n \ge 0} a_n z^n \right) \cdot \left( \sum_{n \ge 0} b_n z^n \right) = \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_k b_{n - k} $$

You can express your double sum in the generating function equation in this way (depending on your $C_{i, n}$), and work from there. Without more details on what the coefficients look like, it is just a mess of subindices.