1
$\begingroup$

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 ?

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

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 ^_^

$\endgroup$
4
  • $\begingroup$ Just for my interrest... is it possible to solve higher order recurrence relation with this technique? $\endgroup$ Nov 16 '20 at 21:06
  • 2
    $\begingroup$ 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) $\endgroup$ Nov 16 '20 at 21:21
  • $\begingroup$ 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. $\endgroup$ Nov 17 '20 at 5:33
  • 1
    $\begingroup$ 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}$ $\endgroup$ Nov 17 '20 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.