# Math Help - Recurrence Relations

1. ## Recurrence Relations

I don't realy understand how to solve recurrence relations. I have the following 2 problems and I don't know how to work them.

1)
$
a_{n} = 6a_{n-1} - 8a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 10
$

2)
$
a_{n} = 2a_{n-1} - a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 1
$

2. #1:

$a_{n}=6a_{n-1}-8a_{n-2}, \;\ a_{0}=4, \;\ a_{1}=10$

$n^{2}-6n+8=0$

$(n-4)(n-2)=0$

$n=4, \;\ n=2$

$a\cdot 4^{n}+b\cdot 2^{n}$

$a\cdot 4^{0}+b\cdot 2^{0}=4$

$a\cdot 4^{1}+b\cdot 2^{1}=10$

Solve the system and we get:

$a+b=4$
$4a+2b=10$

$a=1, \;\ b=3$

$\boxed{4^{n}+3\cdot 2^{n}}$

Can you get the other?. It has 1 as a root of multiplicity 2, so you will need an extra n:

$a\cdot 1^{n}+b\cdot n\cdot 1^{n}$

3. So for number 2:

a * 1^0 + b*(0)*1^0 = 4

so

a = 4

a*1^1 + b(1) * 1^1 = 1

5 + b = 1

b = -4

4 * 2^n - 4 * 1^n

This works for a_0 but not a_1. Where did I go wrong. By the way, thanks so much. Trying to do this on my own and its hard!

4. $n^{2}-2n+1$

$(n-1)^{2}$

The solution(s) is 1 and 1. Remember, I said multiplicity 2?.

$a\cdot 1^{n}+b\cdot n\cdot 1^{n}$

$a\cdot 1^{0}+b(0)\cdot 1^{0}=4\Rightarrow a=4$

$a\cdot 1^{1}+b(1)\cdot 1^{1}=1\Rightarrow a+b=1$

$\therefore a=4, \;\ b=-3$

$\boxed{4-3n}$

5. $
a_{k + 2} = 2 \cdot a_{k + 1} - a_k \Leftrightarrow a_{k + 2} - a_{k + 1} = a_{k + 1} - a_k
$
for all $
k \in \mathbb{N}
$

Since $
a_{k + 2} - a_{k + 1} = a_{k + 1} - a_k
$
we have that the sequence $
b_k = a_{k + 1} - a_k
$
is constant ( that can be done by induction)

So $
a_{k + 1} - a_k = a_1 - a_0=1-4=-3
$
for all $
k \in \mathbb{N}
$

Summing: $
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1} - a_k } \right)} = \left( { - 3} \right) \cdot n
$

On the LHS we have a telescoping sum: $
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1} - a_k } \right)} = \left( {a_1 - a_0 } \right) + \left( {a_2 - a_1 } \right) + ... + \left( {a_{n - 1} - a_{n - 2} } \right) + \left( {a_n - a_{n - 1} } \right)
$

Cancelling out the terms: $
\sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1} - a_k } \right)} = a_n - a_0 = a_n - 4
$

So: $
a_n = -3 \cdot n + 4
$