$$7,19,61,217,817,...$$This infinite sequence is a recurrent sequence. The nth term rule for the sequence is $a_n=\frac{3 \cdot 2^{n}}{2} + \frac{3 \cdot 4^{n}}{4} + 1$, where $n>0$. The recursive formula is $a_n=6 a_{n-1} - 8 a_{n-2} + 3$, where $n>2$, $a_{1}=7$, and $a_{2}=19$.
RECURSIVE FORMULA
Linear Recurrence Relation
[View Steps]
Given a sequence of 5 terms, the recursive formula is of the form $$a_n=x_0 + x_1 a_{n-1} + ... + x_k a_{n-k}, \text{where } 1 \leq k \leq 2$$
When $k=2$: $$a_n=x_0 + a_{n-1} x_{1} + a_{n-2} x_{2}, n > 2$$ $$\begin{aligned}61&=x_{0} + 19 x_{1} + 7 x_{2}\\217&=x_{0} + 61 x_{1} + 19 x_{2}\\817&=x_{0} + 217 x_{1} + 61 x_{2} \end{aligned}$$$$\left\{ x_{0} : 3, \ x_{1} : 6, \ x_{2} : -8\right\}$$
The nth term rule is:$$a_n=6 a_{n-1} - 8 a_{n-2} + 3$$
Given a sequence of m terms, the recursive formula is of the form $$a_n=x_0 + x_1 a_{n-1} + ... + x_k a_{n-k}, \text{where } 1 \leq k \leq \left \lfloor \frac{m-1}{2} \right \rfloor$$
Using all the given terms, solve the systems of equations for $x_i$ when $k=1,...,\left \lfloor \frac{m-1}{2} \right \rfloor$. If $x_i$ is not found for any $k$, a recursive formula cannot be found using this method.
When $k=1$: $$a_n=x_0 + x_1 a_{n-1}, n > 1$$ Solve for $x_0$ and $x_1$: $$\begin{aligned} a_2&=x_0 + x_1 a_1 \\ a_3&=x_0 + x_1 a_2 \\ \vdots \\ a_m&=x_0 + x_1 a_{m-1}\end{aligned}$$
EXPLICIT FORMULA
Non-Homogeneous Solution
[View Steps]
Given a non-homogeneous linear recurrence relation $$a_n=6 a_{n-1} - 8 a_{n-2} + 3$$ the closed formula where $a_h$ is the general solution of $6 a_{n-1} - 8 a_{n-2}$, and $a_p$ is the particular solution of $3$ is $$a_n=a_h + a_p$$
Find $a_h$:
characteristic equation: $r^{2} - 6 r + 8=0$
roots: $\left\{ 2 : 1, \ 4 : 1\right\}, \text{ where r:m}$
general solution: $a_h=2^{n} c_{2} + 4^{n} c_{1}$
Find $a_p$:
trial solution: $t(n)=A$
particular solution: $a_p=1$
$\begin{aligned}A&=6 A - 8 A + 3 \\ A&=1\end{aligned}$
Using the first $2$ terms, solve for $c_i$: $$a_n=2^{n} c_{2} + 4^{n} c_{1} + 1$$ $$\begin{aligned}7&=2^{1} c_{2} + 4^{1} c_{1} + 1\\19&=2^{2} c_{2} + 4^{2} c_{1} + 1\end{aligned}$$ $$\left\{ c_{1} : \frac{3}{4}, \ c_{2} : \frac{3}{2}\right\}$$
The nth term rule is: $$a_n=\frac{3 \cdot 2^{n}}{2} + \frac{3 \cdot 4^{n}}{4} + 1$$
Given a non-homogeneous linear recurrence relation in the form $$a_n=C_1 a_{n-1} + C_2 a_{n-2} + ... + C_k a_{n-k} + f(n), \text{where } f(n)\neq0$$the closed formula where $a_h$ is the general solution of $C_1 a_{n-1} + C_2 a_{n-2} + ... + C_k a_{n-k}$ (homogeneous) and $a_p$ is the particular solution of $f(n)$ is $$a_n=a_h + a_p$$
To find $a_h$, use the Characteristic Root Technique. [ show ]
Given a homogeneous linear recurrence relation of order $k$$$C_1 a_{n-1} + C_2 a_{n-2} + ... + C_k a_{n-k}$$ the characteristic equation is the $k$th degree polynomial equation$$r^k - C_1 r^{k-1} - C_2 r^{k-2} - ... - C_{k-1} r - C_k=0$$
Characteristic Roots
1. If $r$ is a distinct real root, then the general solution includes a term $r^n$.
2. If $r$ is a repeated real root with multiplicity of $m$, then the general solution includes the terms $r^n, n r^n,..., n^{m-1} r^n$.
3. If $r$ is a pair of complex roots, then the general solution includes the terms $|r|^n \sin(n\theta)$ and $|r|^n \cos(n\theta)$ where $r=a\pm b i= |r|e^{\pm \theta i}$.
Let the terms be denoted by $f_i(n)$ where $i=1,...,k$. The general solution is $$a_h=c_1 f_1(n) + c_2 f_2(n) + ... + c_k f_k(n)$$
To find $a_p$, find an appropriate trial solution. [ show ]
1. Choose a reasonable trial solution $t(n)$ for $f(n)$.
Possible Trial Solutions for f(n)
1. Constant
A
2. mth Degree Polynomial
Amnm + ... + A1n + A0
3. Exponential with base b
Abn OR Anbn OR etc.
2. Substitute $a_i = t(i)$ for $i = n, n-1, ..., n-k$ in the recurrence relation, and solve for the missing variables $A_j$.
3. The particular solution is $$a_p=t(n)$$
The closed formula where $c_i$ are coefficients determined by the initial conditions is $$a_n=c_1 f_1(n) + c_2 f_2(n) + ... + c_k f_k(n) + t(n)$$
Solve the systems of equations to find $c_i$: $$\begin{aligned}a_1 &= c_1 f_1(1) + c_2 f_2(1) + ... + c_k f_k(1) + t(1) \\ a_2 &= c_1 f_1(2) + c_2 f_2(2) + ... + c_k f_k(2) + t(2) \\ \vdots \\ a_k &= c_1 f_1(k) + c_2 f_2(k) + ... + c_k f_k(k) + t(k) \end{aligned}$$
