Find a closed form recurrence relation $T(n) = 3T(n - 2) + 2T(n - 3) + 4$; $T(0) = 0$, $T(1) = 0$, $T(2) = 5$.

Question

For two ordered linear recurrence relation is − $F_n= AF_{n−1}+ BF_{n−2}$ where $A$ and $B$ are real numbers.

The characteristic equation for the above recurrence relation is −

$x^2−Ax−B=0$.

However, I don't know how to solve when $F_{n-3}$ is involved. Kindly help

Answer 1

You must solve the homogenceous equation $$t_n=3t_{n-2}+2t{n-3}$$ by the Ansatz $$t_n=q^n$$ and then you have to find a Special solution of the inhomogeneous equation for this make the Ansatz $$t_{n_p}=a+b\times 2^{n+c}$$

Answer 2

Hint:

It is the same situation as for a linear differential equation: the solutions are obtained solving first the homogeneous linear recurrence: $$T(n) = 3T(n - 2) + 2T(n - 3),$$ then adding to the general solution of this homogeneous recurrence equation an particular solution of the non-homogeneous recurrence.

• The solutions of a recurrence of order $3$ are a $3$-dimensional vector space. We first seek for solutions of the form $q^n$, where $q$ is a root of the (cubic) characteristic equation: $$x^3=3x+2,\quad i.e.\enspace x^3-3x-2=0.$$ This particular equation is easily solved by the rational roots theorem.

• If you have $3$ simple roots, you obtain a basis of the vector space of solutions of the homogeneous recurrence, $\{q_1^n,\:q_2^n,\:q_3^n\}$.

  If you have a simple root $a_1$ a double root $q_2$, you must complete the linearly independent system$\{q_1^n,\:q_2^n\}$ by a third (independent) solution, $nq_2^n$.

  If you have a triple root, a basis will be $\{q^n,\;nq^n,\:n^2q^n\}$.

• The non-homogeneous equation as a stanard r.h.s. – a constant, so you may try another constant as a particular solution.