What is the fastest way to solve the following difference equation:
$u_{n+2}$=$\frac{1}{3}*u_{n+1}+\frac{2}{9}*u_{n}$, where $u_{0}$=1,$u_{1}$=1,$u_{2}$=$\frac{5}{9}$
I have experience with linear algebra and such (I am a first year mathematics student)
Thanks in advance
One elementary method that is found, for instance, in most undergraduate discrete math textbooks, uses the so-called characteristic equation associated with the recurrence; in this answer I explained it with an example, though I did not prove that it works. For your recurrence the characteristic equation is $x^2=\frac13x+\frac29$, or, equivalently, $9x^2-3x-2=0$. Solving this, we find that the roots are $\frac23$ and $-\frac13$, so the general form of the solution is
$$u_n=a\left(\frac23\right)^n+b\left(-\frac13\right)^n\;.$$
Now we use the initial conditions $u_0=u_1=1$ to determine $a$ and $b$. When $n=0$ we must have $a+b=1$, and when $n=1$ we must have $\frac23a-\frac13b=1$, or $2a-b=3$. Solving this system we find that $a=\frac43$ and $b=-\frac13$, so that
$$u_n=\frac43\left(\frac23\right)^n-\frac13\left(-\frac13\right)^n=\frac{2^{n+2}+(-1)^{n+1}}{3^{n+1}}\;.$$