<s>[INST] 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...
 [/INST] Here's the inductive step.  Assume the claim is true for $n=k$.  Then we know that
$$9\mid 7^k(3k+1)-1.$$
Consider the case where $n=k+1$.  In this case, the expression is
$$7^{k+1}(3(k+1)+1)-1.$$
Now, let's simplify this expression to
$$7[7^k(3k+1)+7^k\cdot 3]-1.$$
We observe that $7^k(3k+1)$ appears in this expression, which is almost the inductive hypothesis.  By adding and subtracting 1, we get 
$$7[7^k(3k+1)-1+1+7^k\cdot 3]-1.$$
The expression $7^k(3k+1)-1$ is divisible by 9 by the inductive hypothesis, so it can be ignored.  This leaves that we'd like to have 
$$7^{k+1}\cdot 3+6$$ being divisible by $9$.
To prove this, you can do another induction: $7^n\cdot 3+6$ is divisible by $9$ for all $n\geq 1$.  When $n=1$, then this expands to $27$, which is divisible by $9$.
For the inductive case, assume that for $n=k$,
$$9\mid 7^k\cdot 3+6$$ and consider $n=k+1$.
In this case, you have $$7^{k+1}\cdot 3+6=7[7^k\cdot 3]+6.$$
Noticing that $7^k\cdot 3$ is almost the inductive hypothesis, this can be simplified to 
$$7[7^k\cdot 3+6-6]+6.$$
The $7^k\cdot 3+6$ is divisible by $9$ by the inductive hypothesis, and this leaves $7\cdot 6-6=36$, which is divisible by $9$.
</s>