$3^n$ does not divide $4^n+5$ for $n\geq 2$

This follows from an effective abc conjecture. If $4^n+5=3^nm$ then the quality of this $(a,b,c)$-triple is \begin{align*} q(4^n,5,3^nm)&=\frac{\log(3^nm)}{\log(\mathrm{rad}(4^n\cdot5\cdot3^nm))}\geq\frac{\log(4^n+5)}{\log(30m)}=\frac{\log(4^n+5)}{\log(30)+\log(4^n+5)-\log(3^n)} \end{align*} which is larger than 2 for $n\geq9$, larger than 3 for $n\geq20$, and larger than 4 for $n\geq58$. Conjecturally, there are no such $(a,b,c)$-triples.

Below is an unrelated attempt to figure out what's going on algebraic-number-theoretically.

In the ring of integers $\mathbb{Z}[\sqrt{-5}]$, we have the factorization of ideals $$(4^n+5)=(2^n+\sqrt{-5})(2^n-\sqrt{-5}).$$ Let $I=(2^n+\sqrt{-5})$ and let $I^\prime=(2^n-\sqrt{-5})$. Note that $(2\sqrt{-5})\subseteq I+I^\prime$. Then $I+I^\prime$ divides both $(2\sqrt{-5})$ and $(4^n+5)$. However, $(2\sqrt{-5})$ has norm $20$ and $(4^n+5)$ has norm $(4^n+5)^2$ (which is coprime to $20$. Thus, $I+I^\prime=1$ which shows that $I$ and $I^\prime$ are coprime.

Now suppose that $4^n+5$ is divisible by $3^n$. We have the factorization of ideals $$(3^n)=(3,1+\sqrt{-5})^n(3,1-\sqrt{-5})^n$$ where $\mathfrak p=(3,1+\sqrt{-5})$ and $\mathfrak q=(3,1-\sqrt{-5})$ are conjugate prime ideals of $\mathbb{Z}[\sqrt{-5}]$. Since $I$ and $I^\prime$ are coprime, exactly one of the two possibilities holds:

• $\mathfrak p^n$ divides $I$ and $\mathfrak q^n$ divides $I^\prime$
• $\mathfrak q^n$ divides $I$ and $\mathfrak p^n$ divides $I^\prime$

The first case occurs when $n$ is even ($\mathfrak p$ contains both $2^n+\sqrt{-5}$ and $1+\sqrt{-5}$ so $\mathfrak p$ contains $2^n-1$ so $3\bigm|2^n-1$ so $n$ is even). The second case occurs when $n$ is odd ($\mathfrak p$ contains both $2^n-\sqrt{-5}$ and $1-\sqrt{-5}$ so $\mathfrak p$ contains $2^n+1$ so $3\bigm|2^n+1$ so $n$ is odd).

It's a little late here, but hopefully I can shed some light on why I think this is hard or impossible. Looking mod 9 for counterexamples, we can expand the binomial

$$f(n)=5+(1+3)^n = 5+\sum_{k\ge 0}3^k \binom{n}{k} \equiv 5+1+3n = 3(2+n) \mod 9$$

So the only cases we need to consider are when $n\equiv 1 \mod 3$, in other words $n \in 1+3\mathbb{Z}_3$, otherwise it's only divisible by 3 a single time.

First, all $|\cdot|$ in my post are the 3-adic absolute value. Let's reformulate the original question to be $|f(n)|\le 3^{-n}$ as the condition for there to be a counterexample. This suggests to me as $n$ gets larger, we are approaching a root o $f$, and since $f$ can be extended to be a continuous function of $\mathbb{Z}_3$, seen by its Mahler series above let's do that. We can directly solve for a root of $f(x)=4^x+5=0$, since both 4 and -5 are in the region of convergence of the logarithm power series,

$$r = \frac{\ln (-5)}{\ln(4)} \approx $$

1 + 2*3 + 2*3^2 + 3^3 + 3^4 + 2*3^7 + 3^8 + 3^12 + 3^13 + 2*3^14 + 3^17 + 2*3^18 + 2*3^19 + 3^20 + 2*3^22 + 2*3^23 + 3^24 + 3^26 + 2*3^28 + 2*3^29 + 3^31 + 3^32 + 3^36 + 2*3^38 + 3^39 + 3^40 + 2*3^41 + 2*3^42 + 3^44 + 2*3^45 + 2*3^46 + 2*3^48 + O(3^49)

This is the output from the PARI/GP calculator for the input log(-5+O(3^50))/log(4+O(3^50)) I arbitrarily picked about 50 digits of accuracy, but you can get many more without any trouble. The digits of this seems to match your $\varepsilon$ and $\gamma$ sequence mentioned in the question and an answer earlier exactly.

This root is also in $1+3\mathbb{Z}_3$ so it should be near other $n$ by continuity. Let's represent the difference $|r-n|=|h|$, and now write $|f(n)|$ a new way with this root $f(r)=0$.

$$|f(n)| = |f(r)-f(n)| = |4^r-4^n| =|4^n||4^h-1|= \left| \sum_{k\ge 1}3^k\binom{h}{k}\right|$$

$$|f(n)| = \left| 3h \sum_{k\ge 1}\frac{3^{k-1}}{k}\binom{h-1}{k-1}\right|=3^{-1}|h|$$

The series $\sum_{k\ge 0}\frac{3^k}{k+1}\binom{h-1}{k}=\underline{1}+\frac{3}{2}\binom{h-1}{1}+\frac{3^2}{3}\binom{h-1}{2}+\cdots$ has 3-adic absolute value 1 because all binomial terms necessarily have $|\binom{h-1}{k}|\le 1$ and the exponent on $3$ makes all further terms after the first $1$ smaller than the rest, and by ultrametric inequality overtakes.

Now let's combine what we've gained with our reformulation $$|f(n)|= 3^{-1}|r-n| \le 3^{-n}$$

$$|r-n| \le 3^{-n+1}$$

What this says is for there to be a counterexample, $n$ must have all $n-1$ its first 3-adic digits in common with $\frac{\ln (-5)}{\ln(4)}$ in order to be a counterexample. But since $n$ is a natural number, we know its digits after its first $\lfloor \log_3(n)\rfloor$ digits are all $0$. This means in order for a counterexample to exist, there must be a very long string of $n-1-\lfloor \log_3(n)\rfloor$ consecutive $0$s somewhere in the digit expansion of $\frac{\ln (-5)}{\ln(4)}$. I think this is likely irrational and the problem is just as difficult as trying to find a string of repeating digits in say $\sqrt{2}$ in some sort of predictable way, so I doubt it's possible.