Inductive proof of $\,9 \mathrel| 4^n+6n-1\,$ for all $\,n\in\Bbb N$ Prove that for all $n\in\mathbb N$, $9 \mathrel| (4^n+6n-1)$.
I have shown the base case if $n=0$ (which is a natural number for my course).
I'm now trying to prove that $9k=4^n+6n-1$.
I substituted $n+1$ for $n$, and have $4^{(n+1)}+6(n+1)-1$, which equals $4*4^n+6n+5$.
I'm stuck. Is that not the right way to go? I don't know how to get from the “$+5$” to “$-1$” so I can substitute $9k$ to the right side of the equation. Any help would be greatly appreciated.

Below we prove a more general result, because it requires little extra work yet yields great rewards, revealing structure that allows us to see the Binomial Theorem as the essence of the matter.
$\!\!\begin{align}\rm{\bf Theorem}\ \ \  \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + bn + c  &\rm \iff d\mid \color{blue}{(a\!-\!1)^2},\, \color{brown}{a\!+\!b\!-\!1},\, \color{darkorange}{1\!+\!c}\\ &\rm \iff d\mid f(0),\,f(1),\,f(2)\end{align}$
Proof $\ (\Leftarrow)\ $ By induction on $\rm\,n.\,$ The base case $\rm\,n=0\,$ claims that $\rm\, d\mid f(0)= \color{darkorange}{1\!+\!c},\,$ which is true by hypothesis. $ $ Next, assume that $\rm\,\color{#c00}{d\mid f(n)}\,$ as our inductive hypothesis.
Note $\rm\ \ \color{#0a0}{d\mid  f(n\!+\!1)-f(n)}\, =\, a^n(a-1) + b\, =\,  \color{blue}{(a^n\!-\!1)(a\!-\!1)}\, +\, \color{brown}{a\!+\!b\!-\!1}\ $ by hypotheses.
Thus $\rm\ \ \color{#0a0}{d\mid  f(n\!+\!1)-f(n)}\ $ and $\rm\ \color{#c00}{d\mid f(n)}\ $ so $\rm\ d\,$ divides their sum $\rm\,f(n\!+\!1).$
$(\Rightarrow)\,\ \ \rm\, f(0)= \color{darkorange}{1\!+\!c},\,$ $\rm\  f(1)\!-\!f(0) = \color{brown}{a\!+\!b\!-\!1},\ $ $\rm f(2)\!-\!f(1)-(f(1)\!-\!f(0)) = (\color{blue}{a\!-\!1})^2\ \ $ QED

Specializing $\rm\ a,b,c,d = 4,6,-1,9\,$ yields the original problem:
$\rm\qquad\qquad\ 9\mid \color{blue}{(4\!-\!1)^2},\, \color{brown}{4\!+\!6\!-\!1},\,\color{darkorange}{1\!-\!1}\ \ \Rightarrow\ \ 9\mid f(n) = \color{blue}4^n\! + \color{brown}6n  \color{darkorange}{-1},\ \ for\ all\,\ n\in\Bbb N$
The relationship with the Binomial Theorem ($\rm\color{#0a0}{BT}$) becomes obvious if we rewrite the theorem in arithmetical (equational) language, by replacing divisibility relations by equivalent congruences. Rearranging $\rm\ f(n) = a^n\! + b\,n + c\equiv 0\pmod d\, $ we have
$$\begin{eqnarray}\rm mod\ d\!:\ a^n \equiv \color{darkorange}{-c}+n(\color{brown}{-b}) &\equiv&\rm \color{darkorange}1 + n(\color{brown}{a\!-\!1})\quad by\ \ \color{brown}{{-}b\equiv a\!-\!1},\ \ \color{darkorange}{c\equiv -1}\\ 
 \rm but\ \ \ \ a^n\equiv\, (1+a\!-\!1)^n&\rm\overset{\color{#0a0}{BT}}\equiv&\rm 1 + n(a\!-\!1) + \color{blue}{(a\!-\!1)^2}(\cdots)\ \ and\ \ \color{blue}{(a\!-\!1)^2}\equiv 0 \end{eqnarray}$$
Thus the result my be discovered by binomial expansion, then truncating higher powers of $\rm\,a\!-\!1.\,$ Hence the induction in the above proof is essentially a special case of the type of induction that is used to prove the first two terms of the  Binomial Theorem. Indeed, one could rewrite the above proof to make this relationship more explicit. I leave that as an instructive exercise for the reader.
See also here for the slight generalization $\rm\, f(n) =  e \,a^n+\cdots\,$ vs. $\,a^n+\cdots$

Generally as explained here, we deduce that $\rm\,f_n = f(n)\,$ satisfies a monic order $3$ recurrence $\,\rm (S-1)^2(S-a)\,f_n = 0\ $ so $\rm\ f_{n+3} = c_2\, f_{n+2} + c_1\, f_{n+1} + c_0\, f_n\,$ for $\rm \,c_i\in\Bbb Z,\,$ so a simple induction shows $\rm\,f_0,f_1,f_2\equiv 0\iff f_n\equiv 0\,\ \forall n\in \Bbb N,\,$ so the above proof may be viewed as a special case of the uniqueness theorem for recurrences. Thus $\ \rm d\mid f_0,f_1,f_2,\,\ldots\!\iff d\mid f_0,f_1,f_2,\,$ so $\,\rm \gcd(f_0,f_1,f_2,\ldots) = \gcd(f_0,f_1,f_2)$
Those who know a little ring theory may find it useful to view the universal essence of the matter as nothing but the Binomial Theorem in the ring of dual numbers $\rm\,R[x]/x^2.\,$ This ring proves handy when algebraically studying (higher) derivations, tangent/jet spaces, etc.
