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...
 A: ${\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.
A: If $f(n)=7^n(3n+1)-1,$
$\displaystyle af(m)-f(m+1)=\cdots =1-a+7^m[3m(a-7)+a-28]$
$\displaystyle a=1\implies f(m)-f(m+1)=-7^m(18m+27)\equiv0\pmod9$
So, $9|f(m+1)\iff9|f(m)$
Now establish the base case i.e.,$n=1$
Alternatively w/o using induction, $\displaystyle7^n=(1+6)^n\equiv1+6n\pmod9$
$\displaystyle\implies7^n(3n+1)\equiv(1+6n)(3n+1)\equiv1\pmod9$
A: 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$.
A: You don't need any induction to prove this: simple modular arithmetics will do. The assertion is equivalent to $ 7^n(3n+1)\equiv 1\mod 9$.
First note $7$ has multiplicative order $3$ modulo $9$ since $7^3\equiv 1 \mod 9$.
Next $n \equiv 0,\ 1$ or $-1 \mod 3$.


*

*If $n\equiv 0  \mod 3$: $\quad 7^n(3n+1)\equiv 1\cdot (0+1)=1 \mod 9$.

*If $n\equiv 1  \mod 3$: $\quad 7^n(3n+1)\equiv 7\cdot (3+1)=28\equiv 1 \mod 9$.

*If $n\equiv -1  \mod 3$: $\quad 7^n(3n+1)\equiv 4\cdot (-3+1)=-8\equiv 1 \mod 9$.

A: $[7^n(3n+1)-1]_9 = [7]^n [3] [n]+[7]^n -[1]_9 = x$
$[3] [7]^n = [21][7]^{n-1} = [3]_9$
$x = [3] [n]+[7]^n -[1]_9$
$n = 3k \Rightarrow x = [3][3k] + [7]^{3k} - [1]_9 = [343]^k - [1] = [1] - [1] = [0]$ QED
$n = 3k+1 \Rightarrow x = [3][3k] + [3] + [7]^{3k+1} - [1] = [2] + [1][7] = [0]$ QED
$n = 3k + 2 \Rightarrow x = [3][3k] + [6] + [7]^{3k+2} - [1] = [5] + [1][49] = [5] + [4] = [0]$ QED
A: This isn't the greatest solution but still pretty nifty.
Write:
$$
n = 3k + r
$$
Then:
$$
7^n(3n + 1) - 1 \equiv (-2)^n(3n + 1)-1  \pmod{9}
$$$$ \equiv (-2)^{3k+r}(9k+3r+1)-1  \pmod{9}$$
$$ \equiv (-2)^{r}(3r+1)-1  \pmod{9}$$
So now we just need to check $9\:  \vert \: (-2)^{r}(3r+1)-1$ for $ r=0,1,2$ and we're done.
A: 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.
