Maths Olympiad Prep

Library / /58 of 136

Algebra Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

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

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

Solution

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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