0

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$

meta_warrior
  • 3,288
  • 18
  • 34
User
  • 907
  • Do you know linear algebra and matrices? – DanielV Apr 23 '15 at 02:51
  • I know of linear algebra. I am more comfortable with Algebra than any other form of math. Don't know much about matrices. – User Apr 23 '15 at 02:52
  • This may not be a good first math class to take if you are uncomfortable with mathematics, but if you are willing to study 2x of the other students then you can maybe do it. A "college algebra" class may be preferred to take to brush up on your skills before what seems to be a combinatorics class. I recommend having a discussion with your professor. Be honest about what you do and don't remember. – DanielV Apr 23 '15 at 03:16

3 Answers3

2

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.

Claude Leibovici
  • 260,315
0

$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?

DeepSea
  • 77,651
  • One thing that I think would help me is, what does $a_{0} = a_{1} = 2$ mean? – User Apr 23 '15 at 02:27
  • @Omar: We are given some partial info about a sequence of numbers. With this partial info as clues we have to solve the puzzle; The info are two kinds: how the $k$ th term of the sequence is related to the previous two terms; and the other info is what the first two terms are ($a_0$ and $a_1$).

    Solving means getting a formula for the $k$th term $a_k$ directly in terms of $k$ and not in terms of other members of this sequence.

     – P Vanchinathan Apr 23 '15 at 02:44
0

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.

DanielV
  • 23,556
  • I think I understand now. The only part I am confused on is when you got to 2=X 5^1+Y 2^1 and 2=X 5^0+Y 2^0, how did you come up with the answer of -2/3 and 8/3? – User Apr 23 '15 at 04:31
  • $$X + Y = 2 \implies X = 2 - Y \implies 2 = (2 - Y)~5 + 2Y \implies Y = \frac 83 \implies X + \frac 83 = 2 \implies X = -2/3$$. Frankly, this is a fairly high school level task, to solve 2 equations and 2 variables. I really strongly suggest talking to your professor about whether you should be taking a college algebra class instead. You won't enjoy mathematics if you are taking courses that you aren't prepared for. – DanielV Apr 23 '15 at 05:36
  • PS, that's college algebra, not abstract algebra. Make sure not to confuse those. – DanielV Apr 23 '15 at 05:39