Recurrence relation $a_{n+2}=3a_{n+1}-2a_n$

Question

For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence.
So I'm totally lost with this question because every recurrence relation I have tried was sum of two previous terms. Any clear explanation would be greatly appreciated so that I can do this type of question in the future.

Answer 1

With the first two terms are given to you ($a_0=2$ and $a_1=3$), the only coefficients left to find are $a_i$ for $i=2,3,4,5,6$.

Start with $a_2$,

$a_2 = 3a_1 - 2a_0 = 3\cdot3-2\cdot2= 9 -4=5$

then $a_3 = 3a_2 - 2a_1 = 3 \cdot 5 - 2 \cdot 3 = 15-6 = 9$

and so forth. The terms you solve previously carry over to the next iteration, and therefore, solving from the bottom up will work. Let us re-examine $a_3$ in terms of $a_0$ and $a_1$:

$a_3 = 3a_2 - 2a_1 = 3(3a_1 - 2a_0)-2a_1 = 7a_1-6a_0= 21-12 =9$

which is the same as the simple method of carrying answers from iteration to iteration.

EDIT: From (http://people.uncw.edu/tompkinsj/133/recursion/homogeneous.htm),

From the website above, the recurrence relation $a_{n+2} = 3a_{n+1} -2a_{n}$ can be solved with the Distinct Roots Theorem.

Consider $a_{n+k} = t^k$, then the relation becomes $t^2-3t+2=(t-2)(t-1)=0$. The roots, denoted by $r$ and $s$, are $2$ and $1$, respectively. By the Distinct Roots Theorem, the sequence satisfies the following equation $a_{n} = C\cdot r^n+D \cdot s^n=C \cdot2^n +D$.

With the initial terms ($a_0=2$ and $a_1=3$), $C$ and $D$ can be solved for by the following equations:

$a_0 = C\cdot 2^0+D = C+D=2$

$a_1 = C\cdot 2^1+D = 2C+D=3$

$(a_1-a_0) = C =1$

$\implies D = 1$

$\therefore a_n = 2^n + 1^n = 2^n + 1$

Verify with $a_3$: $a_3 = 2^3 +1 = 9$ which is the same as solving the recurrence manually.

Answer 2

Computing the first six terms is well defined. You are given $a_0=2, a_1=3$ and $a_{n+2}=3a_{n+1}-2a_n$. If you substitute $n=2$ you get $a_{2}=3a_{1}-2a_0=3\cdot 3 -2 \cdot 2=5$ and you can keep going. A spreadsheet with copy down will make it easy to get the next terms.

The general solution is like your previous question. In this case, if the solution is $a_n=cr^n$, you finde $cr^2=3cr-2c$ or $r^2-3r+2=0$ with solutions $r=1$ and $r=2$. Then we have $a_n=c_1n+c_2n^2$ and the initial conditions let you find $c_1,c_2$

Answer 3

Use Wilf's "generatingfunctionology" methods. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 3 \frac{A(z) - a_0}{z} - 2 A(z) $$ Solve for $A(z)$ and split into partial fractions: $$ A(z) = \frac{1}{1 - 2 z} + \frac{1}{1 - z} $$ This is just two geometric series: $$ a_n = 2^n - 1 $$