Prove by induction that $\forall n\geq 1,\ 7\mid 3^{2n+1} + 2^{n-1}$

Note that from your assumption you have:

$3^{2k+1} +2^{k-1} = 7p,\quad p\in\mathbb{Z}$

Then you can change the following line you have:

$9 \cdot3^{2k+1} + 2^{k-1} \cdot 2$

into:

$2(3^{2k+1}+2^{k-1})+7\cdot3^{2k+1} = 2\cdot 7p+7\cdot3^{2k+1}=7(2p+3^{2k+1})$

which is divisible by $7$ as required.

Intuitively the induction step can be viewed as an application of the Congruence Product Rule, i.e. applying the rule to multiply the first two congruences yields the third congruence - as sought.

$$ \begin{align}{\rm mod}\,\ 7\!:\qquad\qquad {3^{\large 2}}\, \equiv&\ \ {2}\\[2pt] -3^{\large 1+2n}\equiv&\ \ 2^{\large n-1}\quad {\rm i.e.}\ \ P(n)\\[-4pt] \overset{\rm multiply}\Longrightarrow\,\ {-}3^{\large 1+2({n+1})}\equiv&\ \ 2^{\large {n}}\ \ \ {\rm i.e.}\ \ P({n\!+\!1})\end{align}\ \qquad $$

If we eliminate the language of congruences by substituting inline the below proof of the Congruence Product Rule then we obtain exactly the common proof given in most other answers. Even if congruences are unfamiliar, we can still impose this intuitive arithmetical structure by using the Product Rule in an equivalent divisbility form, namely

$$\begin{align} {\rm mod}\,\ m\!:\, A\equiv a,\, B\equiv b&\ \ \,\Longrightarrow\,\ \ AB\equiv ab\qquad\text{Congruence Product Rule}\\[3pt] m\mid A-a,\ B-b&\,\Rightarrow\, m\mid AB-ab\qquad\text{Divisibility Product Rule}\\[4pt] {\bf Proof}\quad (A-a)B+a(B&-b)\, = AB-ab\end{align}$$

Thus the inductive step need not be pulled out of a hat like magic. Rather, it has intuitive arithmetical content as congruence multiplication. See here for further discussion.

Note: I wrote the congruence proof in the above form (vs. simpler congruence forms) in order to better highlight how other answers are precisely equivalent to applying the Product Rule.