1

I really need help with this question
Would anyone please give a simple step-by-step on how to solve this Recurrence Relation??

$a_n = 2a_{n-1} - 2a_{n-2}$ where $a_0 = 1$ and $a_1 = 3$

It would really be great if someone could explain how to solve this
So far I made it into the characteristic equation:
$r^2 - 2r + 2 = 0$

But not sure where to go or if I am on the right track

Thanks

Alexei Murphy
  • 73

2 Answers2

2

$r^{2}-2r+2=0 \Leftrightarrow (r-1)^{2}=-1 \Leftrightarrow r=i+1=\sqrt{2}e^{i\frac{\pi}{4}}$ or $r=1-i=\sqrt{2}e^{-i\frac{\pi}{4}}$. So $a_{n}=\sqrt{2}^{n}(k_{1} \cos(\frac{n \pi}{4})+k_{2} \sin(\frac{n \pi}{4}))$.Now $a_{0}=1$ so $k_{1}=1$, and similarly you can find $k_{2}$!

mich95
  • 8,713
  • Thanks @mich95, But I'm still unsure about the $a_0$ and $k_1$, what do you do with that?? – Alexei Murphy Jun 08 '15 at 01:23
  • $k_{1}$ is a constant, that appears in the general form of the solution. Now you imposed that $a_{0}=1$, $a_{1}=3$ so you substitute $n$ by $0$, and you set $a_{0}$ equal to $1$, and then you substitute $n$ by 1, and you set $a_{1}=3$, and you get a system with two uknowns that you can solve. In your case, $a_{0}=(\sqrt{2})^{0})(k_{1} \cos 0+k_{2} \sin 0)=1$ then,$1(k_{1} \times 1 +k_{2} \times 0)=1$ so $k_{1}=1$. – mich95 Jun 08 '15 at 01:28
  • http://www.math.northwestern.edu/~mlerma/courses/cs310-04w/notes/dm-recurrences.pdf – mich95 Jun 08 '15 at 01:42
  • Thank you so much @mich95 That really really did help me a lot

    But I'm still just a bit confused about the $i$ part, with the conjugate roots

     – Alexei Murphy Jun 08 '15 at 02:14
  • Could you be more precise? I will be happy to explain it! – mich95 Jun 08 '15 at 02:16
  • I don't really understand about the $i$ part, for the conjugate roots Why would there have to be: $\sqrt {2}e$ ?

    Could you be able to 'break down' the steps about the $i$ ??

     – Alexei Murphy Jun 08 '15 at 02:21
  • Oh, do you know the polar form ? – mich95 Jun 08 '15 at 02:27
  • $|1+i|=\sqrt{2}$ and $\vert 1+i \vert =\sqrt{2}(\frac{1+i}{\sqrt{2}})=\sqrt{2}(\cos \frac{\pi}{4}+i\sin \frac{\pi}{4})=\sqrt{2}e^{i\frac{\pi}{4}}$ – mich95 Jun 08 '15 at 02:32
0

A generatingfunctionological solution would be to define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence shifting indices as:

$$ a_{n + 2} = 2 a_{n + 1} - 2 a_n $$

Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize some sums:

$$ \frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} - 2 A(z) $$

Plug in $a_0 = 1, a_1 = 3$ and solve for $A(z)$ to get

$$ A(z) = \frac{1 + z}{1 - 2 z + 2 z^2} $$

Write this as partial fractions, factoring the denominator as $1 - 2 z + 2 z^2 = (1 - (1 - \mathrm{i}) z) (1 - (1 + \mathrm{i}) z)$:

$$ A(z) = \frac{1 + 2 \mathrm{i}}{2} \cdot \frac{1}{1 - (1 + \mathrm{i}) z} + \frac{1 - 2 \mathrm{i}}{2} \cdot \frac{1}{1 - (1 - \mathrm{i}) z} $$

This is two geometric series, so we can read off the coefficients:

$$ a_n = \frac{1 + 2 \mathrm{i}}{2} \cdot (1 + \mathrm{i})^n + \frac{1 - 2 \mathrm{i}}{2} \cdot (1 - \mathrm{i})^n $$

This is the sum of a complex number and it's conjugate, so it is just twice the real part of the first one:

$$ a_n = 2 \Re\left(\frac{1 + 2 \mathrm{i}}{2} \cdot (1 + \mathrm{i})^n\right) $$

Write the numbers in polar form:

$\begin{align} a_n &= 2 \Re\left( \sqrt{5} \cdot \exp(\mathrm{i} \arctan 2) \cdot \sqrt{2}^n \cdot \exp(\pi n \mathrm{i} / 4) \right) \\ &= 2 \sqrt{5} \cdot \sqrt{2}^n \cdot \Re\left( \exp\left( \left( \frac{n \pi}{4} + \arctan 2 \right) \mathrm{i} \right) \right) \\ &= 2 \sqrt{5} \cdot \sqrt{2}^n \cdot \cos \left( \frac{n \pi}{4} + \arctan 2 \right) \end{align}$

vonbrand
  • 27,812