find the largest integer $m$ such that $2^m$ divides $3^{2n+2}-8n-9$ 
find the largest integer $m$ such that $2^m$ divides $\space 3^{2n+2}-8n-9$ when $n$ is a natural number.

If the answer was known it will be easy induction.
I started out like this :
$\space 3^{2n+2}-8n-9=9(3^{2n}-1)-8n=9\underbrace{(3^n-1)(3^n+1)}-8n$
Now we have $\frac{3^n-1}{3-1}$ is some integer (sum of GP),or
$ 2|\space 3^n-1$
also we have $3^n+1$ is even ,or
$2|3^n+1....(3)$
From this we conclude $4|(3^n-1)(3^n+1) ...(1)$
Let n be even then $3^n-1=3^{2m}-1=(3^m-1)(3^m+1)$,
by $(1)$ :
$4|(3^m+1)(3^m-1)$ meaning $4|3^n-1...........(2)$
combining $(2),(3)$ we have $8|3^{2n+2}-8n-9$
Similarly i was able to work out the same when $n=2m+1$ by noting that $3^n+1=3^{2m+1}+1$ is divisible by $4$.
I got the largest integer as $3$.
But i am wrong as the MCQ did not have the option $m=3$
how do i proceed.
Note: I have  not learnt about fermat's little theorem
Also i am looking for Hints  rather than complete solutions .use of >!  may help
 A: Hint: For $n=1$, it is clear which is the largest power of $2$.  Now consider $(8+1)^{n+1} - [(n+1)\cdot8+1]$ and use binomial expansion to conclude it works for all larger $n$.
A: In such problems, it's common to check for some small values to see if there's a pattern early on. Let's to do that here:
$$\begin{align}
 n=1&: 3^4 - 8- 9 = 64 = 2^6 \\
 n=2&: 3^6 - 16 - 9 = 704 = 64\cdot 11 = 2^6 \cdot11 \\
 n=3&: 3^8 - 24 - 9 = 6528 = 128\cdot 51 = 2^7 \cdot51 \\
 n=4&: 3^{10} - 32 - 9 = 59008 = 128\cdot 461 = 2^7 \cdot461
 \end{align}$$
So far we are seeing that $2^6 = 64$ does the job. Since you said that you could do induction if you knew the answer, I will let you work it out and add the type with spoilers below:

 If $a_n = 3^{2n+2} - 8n - 9$ then $a_{n+1} = 9a_n + 64(n+1)$

A: Let $a_n=3^{2n +2}-8n -9$. Then the power series $f (z )=\sum_{k =0}^{\infty }a_k z^k$ can be written as
$$f(z)=\frac{b_0+b_1 z +b_2 z^2}{(1-c_0 z)(1-c_1 z)(1-c_2z)}$$
for some nonnegative integers $b_i$, $c_j$, and furthermore the common divisors of the $b_i$ are divisors of the $a_n$. Can you take it from there?
