Finding closed formula for the recurrence relations with non-constant coefficient

discrete mathematicsrecurrence-relationssequences-and-series

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 ?

Best Answer

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.

You can read more about this technique in Wilf's fantastic book generatingfunctionology.


I hope this helps ^_^

Related Question