# Math Help - Recurrence Relations

1. ## Recurrence Relations

It's been a while since I stopped by, but when I get 100% stumped I know to turn here. Hoping someone can point me down the right path with this, not only with a solution, but suggestions on reading material (on or offline) to help me learn this content.

Find the solution of the recurrence relation $u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2$, where $u_{0} = 2, u_{1} = 2.$ Express your solution in the form $2^{f(n)} \cos (g(n)\pi)$, where the functions $f$ and $g$ map the non-negative integers onto the reals.

2. ## Re: Recurrence Relations

Originally Posted by Henderson
It's been a while since I stopped by, but when I get 100% stumped I know to turn here. Hoping someone can point me down the right path with this, not only with a solution, but suggestions on reading material (on or offline) to help me learn this content.

Find the solution of the recurrence relation $u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2$, where $u_{0} = 2, u_{1} = 2.$ Express your solution in the form $2^{f(n)} \cos (g(n)\pi)$, where the functions $f$ and $g$ map the non-negative integers onto the reals.
well I solved the thing for you but I don't know that it's going to help you understand general recurrence relations any.

You should be able to put the relation into excel or something and get the sequence it produces.

Doing this I just just determined f and g by inspection.

Are you able to generate the sequence from the recurrence relation?

3. ## Re: Recurrence Relations

I would recommend checking out Method 4 from this website: Wikihow: Solve Recurrence Relations

Method 4 involves solving Linear Recurrences. It suggests the recurrence relation is closely tied to the polynomial $x^2-2x+2$, called the "characteristic polynomial" of the recurrence relation. Solving the characteristic polynomial gives $x = 1\pm i$. Then $u_n = c_1(1+i)^n + c_2(1-i)^n$. Plugging in, $u_0 = 2 = c_1(1+i)^0 + c_2(1-i)^0$ and $u_1 = 2 = c_1(1+i)^1+c_2(1-i)^1$ you have $c_1+c_2 = 2$ and $(c_1+c_2)+(c_1-c_2)i = 2$. This gives $c_1 +c_2 = 2$ and $c_1-c_2 = 0$, so $c_1=c_2 = 1$.

So, you have $u_n = (1+i)^n + (1-i)^n$. In polar notation, you can rewrite this as $u_n = (\sqrt{2}e^{i\pi/4})^n+(\sqrt{2}e^{-i\pi/4})^n$. Then using Euler's Formula, you have:

$u_n = 2^{n/2}(\cos(n\pi/4)+i\sin(n\pi/4)+\cos(n\pi/4)-i\sin(n\pi/4)) = 2^{n/2}(2\cos(n\pi/4))$

This gives $f(n) = 2g(n)+1$ and $g(n) = \dfrac{n}{4}$.

I am not sure if this method is what you had in mind, but it is the simplest method I know.

4. ## Re: Recurrence Relations

Thank you- that is the path I have taken, and finding the roots using the characteristic equation has been something we have practiced in class. I had found the roots of $1+i$ and $1-i$, and the coefficients of $c_{1} = c_{2} = 1$, but stopped there, because when I check my working up to that point, I get different values than the sequence gives me.

For example, when $n=7$:
$u_{7} = 176$

The sequence I've made to get there is
$u_{n}$: $(2, 2, 0, 4, -8, 24, -64, 176)$

But $1 (1 + i) ^7 + 1 (1 - i) ^7$
$= (8 - 8i) + (8 + 8i)$
$=16$

Any thoughts?

5. ## Re: Recurrence Relations

Originally Posted by Henderson
Thank you- that is the path I have taken, and finding the roots using the characteristic equation has been something we have practiced in class. I had found the roots of $1+i$ and $1-i$, and the coefficients of $c_{1} = c_{2} = 1$, but stopped there, because when I check my working up to that point, I get different values than the sequence gives me.

For example, when $n=7$:
$u_{7} = 176$

The sequence I've made to get there is
$u_{n}$: $(2, 2, 0, 4, -8, 24, -64, 176)$

But $1 (1 + i) ^7 + 1 (1 - i) ^7$
$= (8 - 8i) + (8 + 8i)$
$=16$

Any thoughts?
24 is incorrect. 16 is the correct value for $u_7$

6. ## Re: Recurrence Relations

The correct sequence for $u_n$ is $\begin{matrix}n & u_n \\ 0 & 2 \\ 1 & 2 \\ 2 & 0 \\ 3 & -4 \\ 4 & -8 \\ 5 & -8 \\ 6 & 0 \\ 7 & 16 \\ 8 & 32\end{matrix}$

So, you calculated several of the terms incorrectly.

7. ## Re: Recurrence Relations

Oh, honestly. So characteristic equations and complex numbers, I can do, but subtracting 0-4 and getting positive 4 will keep me stuck on a problem for hours.

Never mind. Thanks, all!