First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up into two parts; proving that the $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $9$, and that it's divisible by $11$. Unfortunately, I factor it out and get $10(4\cdot10^{2n} + 9\cdot10^{2n-1} + 5)-45$, which is equal to $10(99k)-45$, but of $99$'s divisors, only $3$ divides $45$.
Is there a more ingenious way to factor this equation so that all of my problems are solved?
Best Answer
Let $f_{n}\equiv4\cdot10^{2n}+9\cdot10^{2n-1}+5$. Then $f_{1}=4\cdot100+9\cdot10+5=495$, and $99\mid495$ so $99\mid f_{1}$. Now, suppose that for some $n\in\mathbb{N}$, $99\mid f_{n}$. Now, since $100\equiv1\text{ mod }99$, \begin{align*} f_{n+1} & \equiv 4\cdot10^{2\left(n+1\right)}+9\cdot10^{2\left(n+1\right)-1}+5\text{ (mod) }99\\ & \equiv 4\cdot10^{2n+2}+9\cdot10^{2n+1}+5\text{ (mod) }99\\ & \equiv 4\cdot10^{2n}\cdot10^{2}+9\cdot10^{2n-1}\cdot10^{2}+5\text{ (mod) }99\\ & \equiv4\cdot10^{2n}+9\cdot10^{2n-1}+5\text{ (mod) }99\\ & \equiv f_n \text{ (mod) } 99 \\ & \equiv 0 \text{ (mod) } 99 \end{align*}