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 $\displaystyle u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2$, where $\displaystyle u_{0} = 2, u_{1} = 2.$ Express your solution in the form $\displaystyle 2^{f(n)} \cos (g(n)\pi)$, where the functions $\displaystyle f$ and $\displaystyle 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 $\displaystyle u_{n} = 2u_{n-1} - 2u_{n-2}, n \geq 2$, where $\displaystyle u_{0} = 2, u_{1} = 2.$ Express your solution in the form $\displaystyle 2^{f(n)} \cos (g(n)\pi)$, where the functions $\displaystyle f$ and $\displaystyle 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 $\displaystyle x^2-2x+2$, called the "characteristic polynomial" of the recurrence relation. Solving the characteristic polynomial gives $\displaystyle x = 1\pm i$. Then $\displaystyle u_n = c_1(1+i)^n + c_2(1-i)^n$. Plugging in, $\displaystyle u_0 = 2 = c_1(1+i)^0 + c_2(1-i)^0$ and $\displaystyle u_1 = 2 = c_1(1+i)^1+c_2(1-i)^1$ you have $\displaystyle c_1+c_2 = 2$ and $\displaystyle (c_1+c_2)+(c_1-c_2)i = 2$. This gives $\displaystyle c_1 +c_2 = 2$ and $\displaystyle c_1-c_2 = 0$, so $\displaystyle c_1=c_2 = 1$.

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

$\displaystyle 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 $\displaystyle f(n) = 2g(n)+1$ and $\displaystyle 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 $\displaystyle 1+i$ and $\displaystyle 1-i$, and the coefficients of $\displaystyle 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 $\displaystyle n=7$:
$\displaystyle u_{7} = 176$

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

But $\displaystyle 1 (1 + i) ^7 + 1 (1 - i) ^7$
$\displaystyle = (8 - 8i) + (8 + 8i)$
$\displaystyle =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 $\displaystyle 1+i$ and $\displaystyle 1-i$, and the coefficients of $\displaystyle 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 $\displaystyle n=7$:
$\displaystyle u_{7} = 176$

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

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

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

6. ## Re: Recurrence Relations

The correct sequence for $\displaystyle u_n$ is $\displaystyle \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!