Given $a_1 = 4$, $a_2 = -2$, and $a_{n} = 2a_{n–2} - 3a_{n–1}$, what is the smallest value of $n$ for which $|a_{n}| > 1\,000\,000$?
I know you can go through and test numbers until you reach 1,000,000. However, is there a way to solve this problem by not merely checking numbers.
If you simplify the expression as much as you can, you should get $$a_n=\frac 1 {34}\big( \left(85-23 \sqrt{17 } \right)\,r_1^n+ \left(85+23 \sqrt{17 } \right)\,r_2^n \big)$$ where $$r_1=-\frac{\sqrt{17}+3}{2} \qquad \text{and} \qquad r_2=\frac{\sqrt{17}-3}{2} $$ You can notice that $r_2$ is quite small. So, for "large" values of $n$, an asymptotic is $$a_n \sim (-1)^{n+1} \,\frac{\left(23 \sqrt{17 }-85 \right)}{34} \left(\frac{\sqrt{17}+3}{2}\right)^n$$ So, if you want $|a_n| \approx 10^k $, taking logarithms you need to compute $n$ such that $$\log(10^k)=\log\left(\frac{23 \sqrt{17 }-85 }{34}\right)+n \log\left(\frac{\sqrt{17}+3}{2}\right)$$ Applied to the case where $k=6$, this would give as a real $n\approx 11.85$. So, $12$ seems to be a good candidate.
But, for $a_n$ itself, you must take care that the sequence alternates between positive and negative numbers.