Track / Stage 7 / 243 of 300 #2123 of 2444

Problem 2123

National Olympiad second round; IMO P1/P4

Algebra Difficulty 7.8 Prove it IMO Hk TST · Hong Kong

a. Using the characteristic equation method or otherwise, find a formula in terms of $n$ for the sequence $a_0 = 1$ , $a_1 = 4$ and $a_{n+2} = 5a_{n+1} - 6a_n$ for $n = 0, 1, 2, \dots$

b. Using the characteristic equation method or otherwise, find a formula in terms of $n$ for the sequence $b_0 = 3$ , $b_1 = 7$ and $b_{n+2} = 4b_{n+1} - 4b_n$ for $n = 0, 1, 2, \dots$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

a.
The answer is $a_n = 2 \cdot 3^n - 2^n$ .
The characteristic equation is $\lambda^2 - 5\lambda + 6 = 0$ . The roots are $\lambda = 3, 2$ . Therefore, we have
$a_n = A \cdot 3^n + B \cdot 2^n$
for some constants $A$ and $B$ . Putting $n = 0$ and $n = 1$ , we need to solve
$\begin{cases} A + B = 1, \\ 3A + 2B = 4. \end{cases}$
We easily deduce $A = (3A + 2B) - 2(A + B) = 2$ and $B = 1 - A = -1$ . Thus, we have
$a_n = 2 \cdot 3^n - 2^n.$

b.
The answer is $b_n = (n + 6)2^{n-1}$ .
The characteristic equation is $\lambda^2 - 4\lambda + 4 = 0$ , with a double root $\lambda = 2$ . Therefore, we have
$b_n = (Cn + D)2^n$
for some constants $C$ and $D$ . Putting $n = 0$ and $n = 1$ , we need to solve
$\begin{cases} D = 3, \\ 2(C + D) = 7. \end{cases}$
Clearly, $C = \frac{7}{2} - D = \frac{1}{2}$ . Thus, we have
$b_n = (n + 6)2^{n-1}.$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.