Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. Show that $a_n$ is always a strictly positive integer.
Problem
Source: 2019 Pan-African Mathematics Olympiad, Problem 1
Tags: recurrence relation, Linear Recurrences, algebra, induction, PAMO
09.04.2019 10:11
Easy to prove, that $a_n=2^{n+1}+(-2)^n$ so $a_n>0$
09.04.2019 20:26
It is also possible to prove by induction that $a_{n + 2} = 4a_n$ for all $n \geq 0$, which also gives us the result.
09.04.2019 21:01
DylanN wrote: It is also possible to prove by induction that $a_{n + 2} = 4a_n$ for all $n \geq 0$, which also gives us the result. I don't see how you got that... putting in $n=0$ we get $24-a_2 -16+12=0=> a_2=20$; this is certainly not equal to $4 \cdot 3$...
09.04.2019 21:11
Sorry, the problem should say that $a_2 = 12$, and not $a_3 = 12$. I'll correct it.
10.04.2020 21:46
By observation, we see that $a_{n+2} = 4a_n$. We proceed to prove this by induction. Clearly, it satisfies the base cases: $4a_0 = a_2$ and $4a_1=a_3$. Now, the inductive step: assume it works for $n$, prove that it works for $n+2$. If $2a_{n+3} - a_{n+2} -8a_{n+1} + 4a_n =0$. This can alternatively be written as: $\frac{a_{n+5}}{2} - \frac{a_{n+4}}{4} -2a_{n+3} + a_{n+2} =0 \implies 2a_{n+5} - a_{n+4} - 8a_{n+3} + 4a_{n+4} = 0$. The result follows. $\blacksquare$
09.09.2020 05:47
We will prove by induction that $a_{n+2}=4a_n$. For the base case, observe that $a_2=4a_0$ is true since $12=4 \cdot 3$. Now, assume that $a_{k+2}=4a_k$ is true for some $n=k$. We have $$2a_{k+3}-a_{k+2}-8a_{k+1}+4a_k=0 \implies 2a_{k+3}-4a_k-8a_{k+1}+4a_k=0 \implies a_{k+3}=4a_{k+1},$$so it holds for $n=k+1$ as well. Hence, $a_{n+2}=4a_n$ holds for all $n$. This means that all the $a_n$ where $n$ is even are positive integers since $a_0$ is positive. Further, we are given that $a_1=3$, so all $a_n$ where $n$ is odd are positive integers as well.
09.09.2020 17:03
we could also use the characteristic equation(by rrt and poly division we get roots are $r = 2, -2, \tfrac{1}{2}$) and systems of equations bash for coefficients.
05.07.2021 17:36
Mehhhh Hint 1:
Hint 2:
Solving for $a_n$ after hint 1 and hint 2, we get $a_n = A.{(\dfrac{1}{2})}^n + B.{-2}^n + C.{2}^n$, substituting the first terms, we easily get $A=0$, hence $a_n = 2^{n+1} + (-2)^n$.
16.04.2024 21:15
$a_3=4*a_1$, $a_5=4*a_3$,..... it is a sequence like that and also; $a_2=a_0*4$, $a_4=4*a_2$,...... It is possible to prove it with induction.