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)
$\displaystyle a_{n} = 6a_{n-1} - 8a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 10$
2)
$\displaystyle a_{n} = 2a_{n-1} - a_{n-2}, for n >= 2, a_{0} = 4 a_{1} = 1$

2. #1:

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

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

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

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

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

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

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

Solve the system and we get:

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

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

$\displaystyle \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:

$\displaystyle 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. $\displaystyle n^{2}-2n+1$

$\displaystyle (n-1)^{2}$

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

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

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

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

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

$\displaystyle \boxed{4-3n}$

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

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

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

Summing: $\displaystyle \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: $\displaystyle \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: $\displaystyle \sum\limits_{k = 0}^{n - 1} {\left( {a_{k + 1} - a_k } \right)} = a_n - a_0 = a_n - 4$

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