<s>[INST] Using induction, prove that $({3^2}^n -1)$ is divisible by $2^{n+2}$ but not by $2^{n+3}$. Question: Using the principle of mathematical induction, prove that for every integer $n\geq 1, ({3^2}^n -1)$ is divisible by $2^{n+2}$ but not by $2^{n+3}$.
My attempt:
Let $P(n): ({3^2}^n -1)$ is divisible by $2^{n+2}$ but not by $2^{n+3}$ ($n\geq 1).$
BASE CASE:
$P(1): ({3^2}^1 -1)$ is divisible by $2^{1+2}$ but not by $2^{1+3}$ , that is, $8$ is divisible by $8$ but not by $16$, which is true.
$\therefore P(1)$ is true
INDUCTION HYPOTHESIS:
Let $P(n)$ be true for $n=k$.
$\therefore P(k)$ is true, that is, $({3^2}^k -1)$ is divisible by $2^{k+2}$ but not by $2^{k+3}$.
$\therefore$ Let ${3^2}^k -1=\lambda.2^{k+2}$
$\implies {3^2}^k=1+\lambda.2^{k+2}$
INDUCTIVE STEP:
$P(k+1):({3^2}^{k+1} -1)$ is divisible by $2^{k+1+2}$ but not by $2^{k+1+3}$
We have to prove that $P(k+1)$ is true
${3^2}^{k+1}-1={3^{{2^k}2}}-1=(1+\lambda.2^{k+2})^2-1=1+2\lambda.2^{k+2}+\lambda^2.2^{2(k+2)}-1=\lambda.2^{k+3}+\lambda^2.2^{k+3+k+1}=2^{k+3}(\lambda+\lambda^2.2^{k+1})$
$\therefore {3^2}^{k+1}-1$ is divisible by $2^{k+3}$
My problem: How do I prove that the number is not divisible by $2^{n+3}$? What should I add to the induction hypothesis part and the inductive step. I am not allowed to use congruence. I am allowed to use the properties of numbers and their division. I thought of doing it by proving that the number leaves a particular remainder on dividing by $2^{n+2}$ but then realized that it would be very cumbersome since the remainder can range from $1$ to $2^{n+3}-1$.
Please help. 
 [/INST] Supose that $3^{2^n}-1$ is not divisible by $2^{n+3}$. Then there are $q\in \mathbb{N}$ and $r\in \{1,2,3,\ldots, 2^{n+3}-1\}$ such that
$$
3^{2^n}-1 = q\cdot  2^{n+3}+r
$$
Then 
\begin{align}
3^{2^{n+1}}-1 =& (3^{2^{n}})^2-1 \\
              =& (3^{2^{n}}-1)(3^{2^{n}}+1) \\ 
              =& (3^{2^{n}}-1)[(3^{2^{n}}-1)+2] \\ 
              =& (q\cdot  2^{n+3}+r)[(q\cdot  2^{n+3}+r)+2]\\
              =& q^2(2^{n+3})^2+2(2^{n+3})r+r^2+2q(2^{n+3})+2r\\
              =& q^2(2^{2n+6})+(2^{n+4})r+r^2+q(2^{n+4})+2r\\
              =& q^2\cdot(2^{n+2})\cdot(2^{n+4})+
                (2^{n+4})\cdot r+r^2+q\cdot(2^{n+4})+2r\\
              =&[q\cdot (2^{n+2})+r+q]\cdot(2^{n+4})+r^2+r
\end{align}
So what can you say about $r^2+r$? Hint. 
A first case is simple. The second case has three subcases.
</s>