Given a sequence of positive integers $$a_1, a_2, a_3, a_4, a_5, \dots$$such that $a_2 > a_1$ and $a_{n+2} = 3a_{n+1} - 2a_n$ for all $n \geq 1$. Prove that $a_{2021} > 2^{2019}$.
Problem
Source:
Tags: Recurrence
NamelyOrange
09.07.2023 19:11
Using characteristic equations, we solve $x^2-3x+2=0\implies(x-1)(x-2)=0\implies x=1,2$. Therefore, $a_n=2^nk+1^nm$ for some value of $\displaystyle k$ and $m$.
Let's assume the scenario where it is most likely that $a_{2021}>2^{2021}$, that is, when $a_n$ grows most slowly. The slowest possible growth we could have (without breaking any of the conditions) is $a_1=1, a_2=2$. In this case, we have $\begin{cases}a_1=1=2^1k+m\\
a_2=2=2^2k+m\end{cases}\implies(k,m) = (0.5, 0)$. Plugging the values of $\displaystyle k$ and $m$ in gives the closed-form equation $a_n=2^{n-1}$. Plugging $n=2021$ to that gives $a_{2021}=2^{2020}$, which is greater than $2^{2019}$.
As for other scenarios, we either have faster rates of growth, or do not get positive integers for $a_n$. And with that, we are done.
. I'm not very experienced in writing proofs, so feel free to critique it! By the way, that was a very cool problem.