Find the smallest $n$ in series, such that $a_n>10^5$

Question

I'm trying to solve the following problem:

We have a series ${a_n}^{\infty}_{n=0}$ with relation: $a_{n+2}=5a_{n+1}+3a_n$; $a_0=a_1=1$. Find smallest $n$, such that $a_n>10^5$.

This is a preparation for exam - no calculators allowed. I tried to create a characteristic polynome, so I created an equation $-x^2+5x+3=0$, however I got roots $x_1=\frac{5-\sqrt{37}}{2}, x_2=\frac{5+\sqrt{37}}{2}$, which I think is wrong, as the numbers don't seem right for an exam.

Did I make a mistake somewhere when creating the equation or is there any other (simpler) way to solve this?

Thanks

Answer 1

I don't know what kind of test this is, but it's not that hard to math out approximately.

$a_2=8$, $a_3=43$, and from there let's assume that the function is $a_{n+1}=5a_n$. So $a_4\approx200$, $a_5\approx1000$, $a_6\approx5000$, $a_7\approx25000$, $a_8\approx125000$. Those are lower bounds, but certainly they're not so far off that $a_7>10^5$ could be true.

Answer 2

You can get an idea of the sequence by computing the first few terms exactly:

$$1,1,8,43,239$$

where $a_4=239=5\cdot43+3\cdot8$ is still easy to do by hand, or even mentally. At this point, some crude estimates can take over:

$$1000\lt a_5\lt1500$$

since $1000=5\cdot200\lt5\cdot239+3\cdot43$ and $1500=5\cdot300\gt5\cdot239+3\cdot43$, and then

$$5000\lt a_6\lt9000$$

since $5000=5\cdot1000\lt5a_5\lt5a_5+3a_4$ and $9000=6\cdot1500\gt5\cdot1500+3\cdot239\gt5a_5+3a_4$

From $5a_6\lt5a_6+3a_5\lt8a_6$, we now have

$$25000\lt a_7\lt72000$$

It now follows that $a_8\gt5a_7\gt125000$ is the first term greater than $10^5$.

Remark: the lower bounds here, $1000, 5000, 25000, 125000$, agree with those in Matthew Daly's answer (which posted while I was initially composing this answer). The upper bounds, $1500,9000,72000$, are the trickier ones to work out -- but only slightly trickier.