# finding closed formula for the recurrence relations with non-constant coefficient

We know writing closed formula for recursive relations.For example;

If $$a_n=7a_{n-2}+6a_{n-3}$$ with $$a_0=9,a_1=10,a_2=32$$ , then closed formula will be equal to

$$a_n=8(-1)^{n}+4(3)^{n}+(-3)(-2)^{n}$$. ( I did not need to write all process here.)

My question is that what would be happen if the coefficients were variables such as $$(n-1) ,(n)$$ instead of $$6,7$$.

Is there any procedure to find the closed formula of recursive relations with non-constant coefficient?

For example ; if the recursion were in the form of $$a_n=(n-1)a_{n-2}+na_{n-3}$$ with $$a_0=9,a_1=10,a_2=32$$ , what would be the closed formula ?

• @Jbag1212 i am not sure about it , the procedure is valid for constant coefficients Nov 16 '20 at 20:20
• @Jbag1212 Not really... Nov 16 '20 at 20:25
• I think, you used characteristic polynomial. Try power series. Nov 16 '20 at 20:28
• This can help math.stackexchange.com/questions/2505629/… Nov 16 '20 at 20:30

I'm not sure what process you used, as different processes generalize differently to this case. I'm personally partial to generating functions, so I'll discuss that method.

The key observation is that coefficients $$(n-1)a_{n-2}$$ look a lot like a derivative. After all, if we let

$$A = \sum a_n x^n$$

Then $$\frac{d}{dx} A = \sum n a_n x^{n-1}$$.

In the example you posed, $$a_n = (n-1)a_{n-2} + na_{n-3}$$, we could multiply everything in sight by $$x^n$$ and sum to get

$$A = \sum a_n x^n = \sum \left ( (n-1) a_{n-2} x^n + n a_{n-3} x^n \right )$$

We split up the right hand side as

$$x^2 \sum (n-1) a_{n-2} x^{n-2} + x^3 \sum n a_{n-3} x^{n-3}$$

Now by using derivative rules, you can simplify this to get a differential equation for $$A$$. Then by solving the differential equation, you can get a closed form for $$A$$. All of this can be automated in a computer algebra system like sage, though you can do it by hand with some persistence.

• If you mean equations with terms that look like $a_i a_j$ then, broadly no. There is no known way to solve those kinds of recurrences in general. The area is closely tied to chaos theory, and closed forms are few and far between (because closed forms tend to be stable with respect to small perturbations, while these kinds of recurrences can be extremely unstable) Nov 16 '20 at 21:21
• I meant sth. like $a_n = a_{n-1} + 3n a_{n-2} + 4(n-1) a_{n-3} + 2(n+1) a_{n-4} +$ ... so with more of these simple terms than just two. Nov 17 '20 at 5:33
• Ah. yes. This same technique will let you solve the kind of recurrence with more than 2 terms that look like $(n-k) a_{n-i}$ Nov 17 '20 at 9:07