0

We are given this linear recurrence relation:

$$U_n=3\cdot U_{n-1}-2\cdot U_{n-2}$$

"Guess" that $U_n = x^n$ is a solution and plug into the recurrence relation:

$$ x^n = 3x^{n-1} - 2x^{n-2} $$

Divide both sides by $x^{n-2}$, assuming $x \ne 0$:

$$ x^2 = 3x - 2 $$

Which is the characteristic equation with roots $1$ and $2$.

Now suppose that the two initial conditions are $U_0=A$ and $U_1=B$.

How can I plug them into the original LRE to obtain the general and particular solution of it ?

Leucippus
  • 26,329
user122424
  • 3,926
  • Note the solution $U_n = 1$ implies that $A = B = 1.$ Can you deduce what must happen for the other? – Sean Roberson Dec 20 '22 at 17:19
  • @SeanRoberson What is $n$ in your $U_n=1$ ? No I cannot yet. – user122424 Dec 20 '22 at 17:21
  • (1). With $x_1=1$ and $x_2=2,$ there are unique $k_1,k_2$ such that $k_1x_1+k_2x_2=U_1$ and $k_1x_1^2+k_2x_2^2=U_2$..... . (2). If $k_1x_n^n+k_2x_2^n=U_n$ and $k_1x_1^{n+1}+k_2x_2^{n+1}=U_{n+1}$ then $k_1x_1^{n+2}+k_2x_2^{n+2}=U_{n+2.}$..... (3). By induction on $n$ and by (1) and (2), therefore $k_1x_1^n+k_2x_2^n=U_n$ forevery $n\in\Bbb Z^+$..... See https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients – DanielWainfleet Dec 20 '22 at 18:28

1 Answers1

1

The "guess" amount to seeking a solution of the form $U_{n} = a \, x_{1}^n + b \, x_{2}^n$ where $x_{1,2}$ are obtained from the "guess". In this case make the assumption that $U_{n}$ has a solution of the form $r^n$, . $$ U_{n+2} = 3 \, U_{n+1} - 2 \, U_{n} \\ r^{n+2} = 3 \, r^{n+1} - 2 \, r^n \\ r^2 - 3 \, r + 2 = 0 \hspace{5mm} r \neq 0 \\ (r-1)(r-2) = 0 $$ showing that the characteristic roots are $\{1, 2\}$ and $$ U_{n} = a \, 1^n + b \, 2^n = a + b \, 2^n.$$

This solution can be checked as follows: \begin{align} 3 \, U_{n-1} - 2 \, U_{n-2} &= 3 \, (a + b \, 2^{n-1}) - 2 \, (a + b \, 2^{n-2}) \\ &= a + b \, 2^{n-2} \, (6 - 2) \\ &= a + b \, 2^n \\ &= U_{n}. \end{align}

Initial conditions: $U_{0} = A$ and $U_{1} = B$ when $U_{n} = a + b \, 2^n$. \begin{align} U_{0} &= A = a + b \\ U_{1} &= B = a + 2 \, b. \end{align} This gives $a + b = A$ and $b = B - A$, or $a = 2 A - B$ and $b = B - A$ and $$ U_{n} = (2 A - B) + (B - A) \, 2^n. $$

Leucippus
  • 26,329