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*}
${\rm mod}\ 9\!:\,\ \overbrace{7^n (1\!+\!3n) \equiv 7^n (1\!+\!3)^n}^{\rm\large Binomial\ Theorem}\! \equiv 28^n\equiv 1^n\equiv 1 $
Remark $ $ We used only the first $2$ terms in the Binomial expansion, and this special case has an easy inductive proof whose inductive step amounts to multiplying by $\,1+a\pmod{\!a^2},\,$ namely
$\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\ (1+ a)^n\, \ \ \equiv&\,\ \ 1 + na\qquad\qquad\,\ \ {\rm i.e.}\ \ P(n)\\[1pt]
\Rightarrow\ \ (1+a)^{\color{}{n+1}}\! \equiv &\ (1+na)(1 + a)\quad\, {\rm by}\ \ 1+a \ \ \rm times\ prior\\
\equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2}\\
\equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\ \ \ {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\[2pt]
\end{align}$
We could substitute this proof inline above (for $\,a=3)\,$ to get an explicit proof by induction on $n\,$ (independent of the Binomial Theorem) but doing so would obfuscate the underlying arithmetic structure, i.e. we should call the Binomial Theorem by name (vs. call-by-value = inline) in order to highlight the key arithmetical structure. The proof is still inductive, but the induction has been encapsulated into a (ubiquitous) Theorem, with the benefit that we can easily reuse it later.
See here for an analogous example using the first three terms of the Binomial Theorem.
Best Answer
I think that if you need to use induction, instead of proving "$4^n+1$ is not divisible by $3$", you should prove the more specific "$4^n+1$ has remainder $2$ when divide by $3$".
$$4^n+1=3k+2\implies4^n=3k+1\implies4^{n+1}=12k+4$$ $$\implies4^{n+1}+1=12k+5\implies4^{n+1}+1=3(4k+1)+2$$