Prove by mathematical induction that $(3n+1)7^n -1$ is divisible by $9$ for integral $n>0$

Question

$7^n(3n+1)-1=9m$

$S_k = 7^k(3k+1)-1=9P$

$\Rightarrow 7^k(3k+1) = 9P+1$

$S_{k+1} = 7\cdot7^k(3(k+1)+1)-1$

$= 7\cdot7^k(3k+1+3)-1$

$= 7\cdot7^k(3k+1) +21\cdot7^k -1$

$= 7(9P+1)+21\cdot7^k -1$

$= 63P+7+21\cdot7^k -1$

$= 63P+6+21\cdot7^k$

$= 9(7P +2/3+21\cdot7^k/9)$

therefore it is divisible by $9$

So I believe I have done this right but I've ended up with non-integers in the answer which im pretty sure isn't right. Where have I gone wrong? Thanks

Answer 1

You're almost finished.

You assume that $S_k = 7^k(3k+1)-1$ is divisible by 9, and therefore divisible by 3.

$S_k = 7^k(3k)+ 7^k-1$ is divisible by 3.

Therefore $7^k-1$ is divisible by 3.

let $3x = 7^k-1$.

$7^k=3x+1$

Then in your final steps:

$=63P+6+21\cdot7^k$

$=63P+6+21(3x+1)$

$=63P+63x+27$

$=9(7P+7x+3)$

Answer 2

It can also be done WITHOUT INDUCTION Il. $$(3n+1)7^n-1$$ $$=(3n+1)(6+1)^n-1$$ Where in expension of $(6+1)^n$ , except last two terms rest will be multiple of $6^2$ $$=(3n+1)(36m+6n+1)-1 ; where \,\,m\in I $$ $$=108mn+6n+3n +1-1=108mn+9n , where \,\,m,n \in I $$ $$= 9K , where \,\, K \in I $$

Answer 3

Another, less elegant way of proving it is using modular arithmetic. In essence, we show that if $$7^n(3n+1)-1\equiv0 \mod9$$ And, for the inductive step, $$7^{n+1}(3(n+1)+1)-1=7^{n+1}(3n+4)-1=7(7^n(3n+1)-1+1+3\cdot7^n)-1$$ Using congruence mod $9$: $$6+3\cdot7^n\equiv0\mod9$$ For all $n\in\mathbb{Z}_9$, which implies what we wanted to show.

Answer 4

To address your question directly:

You calculations are correct but - as you realized by yourself - the conclusion at the end is still not justified since there are fractions in "$= 9(7P +2/3+21\cdot7^k/9)$".

So, just go one step back and try to squeeze out factor $9$, for example, as follows:

\begin{eqnarray}63P+6+21\cdot7^k & = & 63P + 3(2+7^{k+1}) \\ & \stackrel{7^{k+1}=(6+1)^{k+1}=6m+1}{=} & 63P + 3(2+1+6m) \\ & = & 63P + 9(1+2m) \\ & = & 9(7P + 1+2m) \end{eqnarray} Now, the conclusion is justified.