# Finding a Closed Form for a Recurrence Relation

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

• You would attack the change of order of summation the same way you would integration -- including figuring out what region of $\mathbb{Z}^2$ is being summed over and modifying the limits of summation to make sense when reversed: $\sum_{i=0}^\infty \sum_{n=i+1}^\infty$. – Eric Towers Jul 5 '14 at 21:44
• @EricTowers Can that be used to solve the problem though? I'm having trouble doing so, but I feel like it should work. – user142299 Jul 5 '14 at 21:56
• @NotNotLogical: I haven't looked at it -- I only considered the question about the order of summation, which is why I didn't post an answer. – Eric Towers Jul 5 '14 at 22:05

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

• Note that the question was changed. The constants $C$ depend on $n$ as well, so you cannot pull out the factor of $C$ in equation $(1)$. – user142299 Jul 5 '14 at 22:43
• @NotNotLogical You are right. I wish that $C_{i,n}$ be an add-on question to the existing question $C_i$ so that so that we do not need to make drastic changes to our answers. – mike Jul 5 '14 at 23:01

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.

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.