A simple proof by induction $P(n) = \frac{6^{2n} - 3^n}{11} \in \mathbb{N}$

Question

Verify by induction that $P(n) = \frac{6^{2n} - 3^n}{11} \in \mathbb{N} \quad \forall n \ge 1 \in \mathbb{N}$

Basis: $P(1) \Rightarrow \frac{33}{11} \in \mathbb{N}$.

Induction: if the statement holds for some $n$ $\Rightarrow$ holds for $n+1$

I would appreciate some small hints because I'm stuck at $P(n+1) = \frac{6^{2(n+1)} - 3^{n+1}}{11}$

Answer 1

Because $\displaystyle \frac{6^{2n}-3^n}{11}$ is a natural number, we can write for some $k \in \mathbb N, 6^{2n} =3^n +11k $. Then our proof becomes $$\frac {6^{2n+2}-3^{n+1}}{11} = \frac {36 (3^n +11k )-3 (3^{n})}{11} =\frac {33 (3^n) +11 (36k)}{11} \in \mathbb N $$ And thus the proof is completed. Hope it helps.

Answer 2

So the statement $P(n)$ could also be formulated that $11$ divides $6^{2n} -3^n$. So $P(n+1)$ would consider \begin{align} 6^{2(n+1)} - 3^{n+1} & = \\ 6^{2n} \times 36 - 3 \times 3^n & = \\ 3(12 \times 6^{2n} - 3^n )&= \\ 3(11\times 6^{2n} + 6^{2n} - 3^{n}) & = \ldots \end{align} Can you use $P(n)$ in order to prove $P(n+1)$?

Answer 3

HINT

From $$x^{n+1}-y^{n+1}=(x^n+y^n)(x-y)+xy(x^{n-1}+y^{n-1})$$

We have

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

We use induction: If $n-1$ is true, $n+1$ is true.

Answer 4

We have $P(n)=\frac{6^{2n}-3^n}{11} \in \mathbb{N}$.

You have proven that the base case is true.

Now, assume true for $n=k$.

$$6^{2k}-3^k=11p \tag{1}$$

Where $p \in \mathbb{N}$.

True for $n=k+1$.

$6^{2(k+1)}-3^{k+1}=6^{2k+2}-3^{k+1}=36 \cdot 6^{2k}-3 \cdot 3^k \tag{2}$

Now, here comes the trick.

We can substitute from $6^{2k}$ from equation $(1)$ into equation $(2)$.

$$36 \cdot (11p+3^k)-3 \cdot 3^k=11\cdot 36p+36\cdot 3^k-3 \cdot 3^k=11 \cdot 36p-33 \cdot 3^k \tag{3}$$

Since $11\cdot 36p$ is obviously divisible by $11$, and $33 \cdot 3^k$ can be divided by $11$ to give $3 \cdot 3^k$, the whole of equation $(3)$ is divisible by $11$.

Hence, we are done.

Answer 5

You don't really need induction, or just use some simple production, as $$6^{2n}-3^n=3^n(12^n-1)$$

Answer 6

${\rm mod}\ 11\!:\ 6^{\large 2}\!\equiv 3\,\Rightarrow\, (6^{\large 2})^{\large N}\!\equiv 3^{\large N} $ by the Congruence Power Rule (it has a trivial inductive proof).

Remark $\ $ Some of the other answers essentially do the same, except they eliminate the congruence language, and directly inline the proof of the Power Rule (or its inductive basis - the Congruence Product Rule), i.e. they are presented in divisbility "assembly language" instead of higher-level arithmetical language. This viewpoint is discussed at length in this answer.