# Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N}$, using induction.

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?

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*}

Assuming that $4\times10^{2n}+9\times10^{2n-1}+5=99k$, $$4\times10^{2(n+1)}+9\times10^{2(n+1)-1}+5=4\times10^{2n+2}+9\times10^{2n+1}+5=100\times(4\times10^{2n})+100\times(9\times10^{2n-1})+5=100\times(4\times10^{2n}+9\times10^{2n-1})+5=100\times(4\times10^{2n}+9\times10^{2n-1}+5-5)+5=100\times(4\times10^{2n}+9\times10^{2n-1}+5)-500+5=100\times99k-495=100\times99k-5\times99=(100k-5)\times99.$$

Base case: $n=1$: $4 \cdot 10^2 + 9 \cdot 10^{1}+5 = 495$, and $99|495$.

Induction step: $n=k$: Suppose $99|4 \cdot 10^{2k} + 9 \cdot 10^{2k-1}+5$.

Then you need to show it is also true for $n=k+1$.

A number is a multiple of $9$ iff the sum of its decimal digits is a multiple of $9$. Your numbers satisfy this: $4+9+5=18$.

A number is a multiple of $11$ iff the alternating sum of its decimal digits is a multiple of $11$. Your numbers satify this: $4-9+5=0$.

Explicitly, we have $4900\cdots05=9\cdot 544\cdots45$ and $4900\cdots05=11\cdot 4454\cdots5455$.

Or directly, $4900\cdots05=99\cdot 4949\cdots495$, which is the formula given by Martin.