You are given the sequence defined by the following recurrence relation: $$a_n = \cases{a_0 = 1\\a_1 = 3\\a_{n+1} = 5a_n + a_{n-1}, \forall n \geq 1}$$ You are then asked to prove that $123456789 \notin a_n$.
One thing I noticed is that all the numbers belonging to this sequence are made up by a multiple of $5$ plus another number, that is itself a multiple of $5$ plus another number, going down recursively until the number added is $1$ or $3$. There has to be some other similar property that all numbers in this sequence abide by, which $123456789$ doesn't, that can be used to shown it doesn't belong to the sequence.
Any ideas?
Take it modulo $5$.
You'll get $$a_n\equiv1,3$$ and be healthy!