Mathematical Induction

When n=1, (3 x 1 + 1) x 7^1 - 1 = 4 x 7 -1 = 27 is divisible by 9
Therefore, n=1 is true.

Suppose n=k is true. => (3k+1)7^k-1 is divisible by 9.

Now let n=k+1. [3(k+1) + 1] x 7^(k+1) - 1
=(3k+3+1)7^(k+1) - 1
=3k x 7^k x 7 + 3 x 7^(k+1) + 7^k x 7 -1
=3k x 7^k + 6 x 3k x 7^k + 3 x 7^(k+1) + 7^k + 6 x 7^k - 1
=3k x 7^k + 7^k - 1 + 18 x k x 7^k + 21 x 7^k + 6 x 7^k
=(3k+1)7^k-1 + 18k x 7^k + 27 x 7^k

Since (3k+1)7^k-1 is divisible by 9, 18k x 7^k is divisible by 9, 27 x 7^k is divisible by 9,
Therefore, n=k+1 is true.

Therefore, by induction, (3n+1)7^n-1 is divisible by 9 for all natural numbers n.