I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$
I believe that $u_3 = 19$, if I'm correct, but after that I'm stuck. Could someone please help me figure the next two terms and the closed formula for this sequence.
On
You are correct that $u_3=5u_2-6u_1=5\cdot 5-6\cdot 1=19$. Now $u_4=5u_3-6u_2$ and you know the terms on the right. Keep going. A spreadsheet with copy down makes this easy.
On
You're correct in thinking that $u_3 = 19$. In a similar fashion, $u_4 = 5\cdot 19 -6\cdot 5 = 95$ and $u_5 = 5\cdot 65 - 6\cdot 19 = 211$.
To find the general solution, we rewrite the recurrence as $u_n - 5u_{n-1} +6u_{n-2} = 0$. This has auxiliary quadratic equation $x^2-5x+6 = (x-2)(x-3)$, so the recurrence is satisfied by something of the form $A2^n + B3^n$. Using your initial conditions, you can solve for $A$ and $B$.
If you've not seen methods like this (they're similar to solving ODEs), see here.
On
You can get the general term by using generating functions. Define $U(z) = \sum_{n \ge 0} u_n z^n$. Write your recurrence as: $$ u_{n + 2} = 5 u_{n + 1} - 6 u_n \qquad u_0 = 0, u_1 = 1 $$ (it is convenient to start the sum at $n = 0$; the value of $u_0$ comes from running the recurrence backwards).
Multiply the recurrence by $z^n$ and sum over $n \ge 0$. Recognize: \begin{align} \sum_{n \ge 0} u_{n + 1} z^n &= \frac{U(z) - u_0}{z} \\ \sum_{n \ge 0} u_{n + 2} z^n &= \frac{U(z) - u_0 - u_1 z}{z^2} \end{align} and you get: $$ \frac{U(z) - z}{z^2} = 5 \frac{U(z)}{z} - 6 U(z) $$ Solving for $U(z)$ and splitting in partial fractions gives: $$ U(z) = \frac{1}{1 - 3 z} - \frac{1}{1 - 2 z} $$ This is just two geometric series: $$ u_n = 3^n - 2^n $$
On
Regarding a closed form:
The OP's equation is a linear homogeneous recurrence relation with constant coefficients.
A technique for solving relations of the form $u_n + Au_{n-1} + Bu_{n-2} = 0$ is to assume $u(n) \propto k^n$ for some value(s) of $k \ne 0$ which we are going to find.
Substituting our guess into the recurrence relation, $$ k^n + Ak^{n-1} + Bk^{n-2} = 0 \;\forall n \ge 3 $$ Dividing through by $k^{n-2}$ (which is non-zero because $k$ is non-zero by assumption), we get the characteristic polynomial of the recurrence relation: $$ k^2 + Ak + B = 0 $$
Solving this will give different solutions for $u(n)$ depending on the roots of this quadratic.
Going back to the OP's question: $A=-5$ and $B=6$, so $k^2 - 5k + 6 = (k-2)(k-3) = 0$, so $k=$ 2 or 3.
Thus, the general solution to the OP's original equation is: $$ u(n) = \alpha2^n + \beta3^n $$ for some constants $\alpha, \beta$. Substituting in the given initial conditions,
$$ 1 = 2\alpha + 3\beta, \; \; 5 = 4\alpha + 9\beta $$ giving $\alpha = -1$, $\beta = 1$, and so $$ u(n) = 3^n - 2^n $$
So as expected, $u(3) = 27-8=19$, and so on.
The recurrence is given by:
$$u_n = 5 u_{n-1} - 6 u_{n-2}$$