Prove by induction that $3^{n^{2}}+9n+6$ is divisible by 6.

Question

I am having trouble with the induction part of the proof that the expression bellow is divisible by 6 $$ 3^{n^{2}}+9n+6 $$ $n->n+1$ $$ 3^{n^{2}+2n+1}+9n+9+6 $$ I have been able to see that this is divisible by $3$, so if I would be able to find that it is also divisible by $2$ I would prove it.

Answer 1

This is not so. Taking $n = 4$ prompts $$3^{16} + 9(4) + 6\mod 6 = 3.$$

Answer 2

Your statement is NOT true, because for $n=2$ we have $$ 3^{2^2}+2(9)+6=3^4+18+6=81+24=105=102+3=6\cdot17+3. $$

Answer 3

Actually, for all even $n$, $3^{n^2}$ is an odd number and $9n+6$ is an even number, the sum is an odd number and cannot be divided by 6.

Answer 4

$3^{(n+1)^2} + 9(n+1) + 6 =$

$3^{n^2 + 2n + 1} + 9n + 6 + 9 =$

$3^{n^2}3^{2n}*3 + 9n + 6 + 9 =$

$(3^{n^2} + 9n + 6) + (9 + (3^{2n}*3 - 1)3^{3n^2})=$

Now $(9 + (3^{2n}*3 - 1)3^{3n^2})$ is odd so not divisible by 6.

But we have proven that $3^{(n+1)^2} + 9(n+1) + 6$ is even if and only if $3^{n^2} + 9n + 6$ is odd.

So as $3^{n^2} + 9n + 6$ is divisible by 3, and $3^{1^2} + 9*1 + 6$ is even, $3^{n^2}+9+6$ is divisible by $6$ if $n$ is odd, and is not if $n$ is even.

===

To restate the problem:

Prove by induction that $3^{n^2} + 9n + 6$ is divisible by $6$ if $n$ is odd.

$3^{1^2} + 9*1 + 6 = 18$ is divisible by 6$.

Assume $3^{(2k - 1)^2} + 9(2k -1 ) + 6$ is divisible by $6$

The $[3^{(2k + 1)^2} + 9(2k+1) + 6] - [3^{(2k - 1)^2} + 9(2k-1) + 6]=$

$3^{4k^2}*3[3^{2k} - 3^{-2k}] + 18=$

$3^{4k^2 - 2k}[3^{4k} - 1] + 18$ So $k \ge 1$, $3^{4k} - 1$ is even, and $3^{4k^2 - 2k}$ is a non-trivial power of $3$ so $3^{4k^2 - 2k}[3^{4k} - 1]$ is divisible by $6$ and $18$ is divisible by $6$ and as the difference between $3^{(2k + 1)^2} + 9(2k+1) + 6$ and $3^{(2k - 1)^2} + 9(2k -1 ) + 6$ is divisible by $6$ and $3^{(2k - 1)^2} + 9(2k -1 ) + 6$ is divisible by $6$.... we can conclude $3^{(2k + 1)^2} + 9(2k +1 ) + 6$ is divisible by $6$.

....

Of course it'd be easier to simplify before doing the induction:

$3^{n^2} + 9n + 6 = (3^{n^2 - 1} + 3n + 2)$ is divisible by $3$ so proving it is is divisible by $6$ is a matter of proving it is even. As $n$ is odd $9n + 6$ is odd so it is a matter of proving $3^{n^2}$ is odd which... um, it is. No, need for induction at all.

Answer 5

$\begin{align}{\bf Hint}\ \ \ {\rm mod}\,\ 6\!:&\ \ \ 3^{\large f(n)} \equiv\overbrace{-6-9n}^{\large \equiv\,\ 3\color{#c00}n}\ \ \ {\rm for }\ \ f(n)\ge 1\\ \overset{\ {\rm cancel}\,\ \large 3\ } \iff {\rm mod}\,\ 2\!:&\ \ \ \underbrace{3^{\large f(n)-1}}_{\large \equiv\ 1}\equiv \color{#c00}n\iff n\rm\ is\ odd \end{align}$