Exercise 4.4.11 (Linear recurrence of order 3)

Question

Extend the method to prove Theorem 4.10 to derive a formula for $u_n$ if $u_0 = 1,\ u_1 = 2,\ u_2 = 1$, and $u_n = u_{n-1} + 4u_{n-2} - 4 u_{n-3}$ for all integers $n\geq 3$.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

The characteristic polynomial associate to this sequence is
$$p(x) = x^3 - x^2 - 4x + 4 = (x-1)(x-2)(x+2).$$
The three roots of $p(x)$ are $\lambda = 1,\ \mu = 2,\ 
u = -2$
Since $p(x)$ has three distinct simple roots, the generalized Theorem 4.10 shows that there exist three complex numbers $a, b, c$ such that for all $n \in \N$,
$$u_n = a \lambda^n + b \mu^n + c 
u^n = a + b 2^n + c (-2)^n.$$
The coefficients $a,b,c$ are solutions of the system
$$
\left\{
\begin{array}{ll}
1 &= a + b + c,\
2 &= a \lambda + b \mu + c 
u,\
3 & = a\lambda^2 + b \mu^2 + c 
u^2,
\end{array}
ight .
$$
that is
$$
\left\{
\begin{array}{ll}
1 &= a + b + c,\
2 &= a  + 2b  -2c,\
3 & = a + 4b +4 c.
\end{array}
ight .
$$
Since the three roots are distinct, the determinant of this system is the nonzero Vandermonde determinant
$$
D = \begin{vmatrix}  1 & 1 & 1 \ \lambda & \mu & 
u\ \lambda^2& \mu^2 & 
u^2\end{vmatrix} =(\mu - \lambda)(
u - \lambda)(
u - \mu) 
e 0.
$$
Here $D = (2-1)(-2-1)(-2-2) = 12$. 
The unique solution of this system is
$$a = 1,\qquad b = 1/4, \qquad c = -1/4,$$
thus, for all $n \in \N$,
\begin{align*}
u_n &= \frac{1}{4}(4 + 2^n - (-2)^n)\
&=1 + 2^{n-2} - (2)^{n-2}.
\end{align*}

\end{proof}

Exercise 4.4.11 (Linear recurrence of order 3)

Answers

Comments

Exercise 4.4.11 (Linear recurrence of order 3)

Answers

Comments

Add answer