Proving that $7^n(3n+1)-1$ is divisible by 9 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...
${\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&amp;\,\ \ 1 + na\qquad\qquad\,\ \  {\rm i.e.}\ \ P(n)\\[1pt]
\Rightarrow\ \ (1+a)^{\color{}{n+1}}\! \equiv &amp;\  (1+na)(1 + a)\quad\, {\rm by}\ \ 1+a \ \ \rm times\ prior\\ 
\equiv &amp;\,\ \ 1+ na+a+n\color{#c00}{a^2}\\ 
 \equiv &amp;\,\ \ 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.
First, show that this is true for $n=1$:

$7^1\cdot(3\cdot1+1)-1=9\cdot3$

Second, assume that this is true for $n$:

$7^n\cdot(3n+1)-1=9k$

Third, prove that this is true for $n+1$:

$7^{n+1}\cdot(3(n+1)+1)-1=$

$7^{n+1}\cdot(3n+3+1)-1=$

$7^{n+1}\cdot(3n+1+3)-1=$

$7^{n+1}\cdot(3n+1)+7^{n+1}\cdot(3)-1=$

$7\cdot\color{red}{7^n\cdot(3n+1)}+3\cdot7^{n+1}-1=$

$7\cdot(\color{red}{9k+1})+3\cdot7^{n+1}-1=$

$63k+7+3\cdot7^{n+1}-1=$

$63k+3\cdot7^{n+1}+6=$

$\color{blue}{3(21k+7^{n+1}+2)}$

Now:


$7\equiv1\pmod3\implies$
$\forall{m}\in\mathbb{N}:7^m\equiv1\pmod3\implies$
$7^{n+1}\equiv1\pmod3\implies$
$7^{n+1}+2\equiv3\pmod3\implies$
$7^{n+1}+2\equiv0\pmod3\implies$
$3|7^{n+1}+2\implies$
$\exists{p}\in\mathbb{N}:7^{n+1}+2=3p\implies$
$3(21k+7^{n+1}+2)=3(21k+3p)=3(3(7k+p))\color{blue}{=9(7k+p)}$




Please note that the assumption is used only in the part marked red.