1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

$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}$!

$\endgroup$
  • $\begingroup$ Thanks @mich95, But I'm still unsure about the $a_0$ and $k_1$, what do you do with that?? $\endgroup$ – Alexei Murphy Jun 8 '15 at 1:23
  • $\begingroup$ $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$. $\endgroup$ – mich95 Jun 8 '15 at 1:28
  • $\begingroup$ math.northwestern.edu/~mlerma/courses/cs310-04w/notes/… $\endgroup$ – mich95 Jun 8 '15 at 1:42
  • $\begingroup$ 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 $\endgroup$ – Alexei Murphy Jun 8 '15 at 2:14
  • $\begingroup$ Could you be more precise? I will be happy to explain it! $\endgroup$ – mich95 Jun 8 '15 at 2:16
0
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.