How to solve recurrence relation $a_{k}=7a_{k-1}-10a_{k-2}, \forall k\ge2$ with $a_{0} = a_{1} = 2$

Question

Unfortunately I have no idea where to even start with this. This is my first math class in almost a decade. Can anybody tell me how i would go about solving for the following recurrence relation? All help greatly appreciated.

$a_{k}=7a_{k-1}-10a_{k-2}, \forall k\ge2$ with $a_{0} = a_{1} = 2$

Answer 1

Using the classical approach, start with the corresponding characteristic equation. If $$a_{k}=7a_{k-1}-10a_{k-2}$$ then $$r^2=7r-10$$ the roots of which being $2$ and $5$. So, the general form is $$a_k=c_1 2^k+c_2 5^k$$ Now, apply the conditions for $a_0$ and $a_1$; they will give you two linear equations with $c_1,c_2$ as unknwowns.

Answer 2

$a_k - na_{k-1} = m(a_{k-1} - na_{k-2}) \to m+n=7,mn = 10 \to n = 5, m = 2 \to a_k - 5a_{k-1} = 2(a_{k-1} - 5 a_{k-2})$. Put $b_k = a_k - 5a_{k-1} \to b_k = 2b_{k-1},k \geq 2, b_1 = 2 - 2\cdot 5 = 2 - 10 = -8$. Thus $b_k = b_1\cdot 2^{k-1} = -8\cdot 2^{k-1}$. Can you continue?

Answer 3

If you don't mind using matrices, you can combine:

$$a_{k+1} = 7~a_{k} - 10~a_{k-1}$$ with $$a_{k} = a_{k}$$

To get:

$$\begin{align} a_{k+1} &= 7~a_k - 10~a_{k-1} \\ a_{k} &= 1~a_k + 0~a_{k-1} \end{align}$$ $$\begin{align} \begin{bmatrix} a_{k+1} \\ a_{k} \end{bmatrix} % &= \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{k} \\ a_{k-1}\end{bmatrix} % \\ &= \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{k-1} \\ a_{k-2}\end{bmatrix} % \\ &= \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{k-2} \\ a_{k-3}\end{bmatrix} % \\ \vdots % \\ &= \begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix}^k \begin{bmatrix} a_{1} \\ a_{0}\end{bmatrix} % \end{align}$$

The eigenvalues of $\begin{bmatrix} 7 & -10 \\ 1 & 0 \end{bmatrix}$ are $5$ and $2$, so for some matrix $P$:

$$\begin{bmatrix} a_{k+1} \\ a_{k} \end{bmatrix} % = P~\begin{bmatrix} 5 & 0 \\ 0 & 2 \end{bmatrix}^k~P^{-1} \begin{bmatrix} a_{1} \\ a_{0}\end{bmatrix}$$

So for some numbers $X$ and $Y$:

$$a_{k+1} = X~5^k + Y~2^k$$

You can use the initial conditions $a_0 = a_1 = 2$ to find $X$ and $Y$:

$$2 = X~5^1 + Y~2^1$$ $$2 = X~5^0 + Y~2^0$$

To get:

$x = \frac{-2}{3}$ and $y = \frac{8}{3}$

to get the total solution:

$$a_{k+1} = -\frac{2}{3}~5^k + \frac{8}{3}~2^k$$

If you aren't comfortable with matrices, and just want "how do I do this" rather than "why does this work", then I recommend Claude's answer.