I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9.
Usually with these divisibility induction problems, it falls apart nicely and we can easily factorise say a 9 if the question required us to prove that the expression is divisible by 9. However in this case, I do not end up with such a thing.
My work so far below:
Inductive Hypothesis: $7^k(3k+1)-1=9N$ where $N\in\mathbb{N}$
Inductive Step:
$7^{k+1}(3k+4)-1 \\ =7\times 7^k(3k+1+3)-1 \\ =7\times \left [ 7^k(3k+1)+3\times 7^k \right ] -1 \\ = 7 \times \left [ 9N+1 + 3 \times 7^k \right ] -1 \\ = 63N+21\times 7^k+6 \\ = 3 \left [ 21N+7^{k+1}+2 \right ]$
So now I need to somehow prove that $21N+7^{k+1}+2$ is divisible by 3, but I'm not quite sure how to proceed from here…
Best Answer
${\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.