Proving that $64$ divides $3^{2n+2}+56n+55$ by induction Let $n ≥ 0$ be an integer. Prove by induction: 64 divides $3^{2n+2} + 56n + 55$
general expression: $3^{2n+2} + 56n + 55 = 64m$
1st I substitute $P(0)$ and it gives me true:
$9+55 = 64$ (if m = 1 the condition is true)
2nd I assume $n = k$ and I substitute saying $3^{2k+2} + 56k + 55$
and then I don't know what to do to prove the claim.
 A: Notice,  
Assume that for $n=k$, the given natural number $(3^{2n+2}+56n+55)$ is divisible by $64$ then we have 
$$3^{2k+2}+56k+55=64\lambda\tag 1$$
Where, $\lambda$ is an integer. 
Now, substituting $n=k+1$ in the given number, we get 
$$3^{2(k+1)+2}+56(k+1)+55$$$$=3^{2k+4}+56k+56+55$$
$$=9\cdot 3^{2k+2}+56k+56+55$$
$$=9\cdot 3^{2k+2}+(9\cdot 56k-8\cdot 56k)+(9\cdot 55-8\cdot 56)+56$$
$$=(9\cdot 3^{2k+2}+9\cdot 56k+9\cdot 55)-8\cdot 56k-8\cdot 55+56$$
$$=9(3^{2k+2}+ 56k+55)-64\cdot 7k-64\cdot 6$$
setting $3^{2k+2}+ 56k+55=64\lambda$ from (1),
$$=9(64\lambda)-64(7k-6)$$
$$=64(9\lambda-7k+6)=64m$$  where, $m=9\lambda-7k+6$ is some integer 
The above number is divisible by $64$
Hence, the given number $3^{2n+2}+ 56n+55$ is divisible by $64$ $\forall \ \ n\ge 0$   
A: If $f(m)=3^{2m+2}+56m+55,$
$f(n+1)-9\cdot f(n)=3^{2(n+1)+2}+56(n+1)+55-9\cdot(3^{2n+2}+56n+55)$
$=-56n(9-1)+56-55(9-1)$
$=-7\cdot8n\cdot8+56-(56-1)8\equiv0\pmod{64}$
$\implies64\mid f(n+1)\iff64|f(n)$
Now for the base case, set $m=0$
A: By the binomial theorem, $9^{n+1}=(8+1)^{n+1}=64a+8(n+1)+1=64a+8n+9$.
Thus,
$3^{2n+2}+56n+55=$
$=9^{n+1}+56n+55$
$=64a+8n+9+56n+55$
$=64a+64n+64$
$=64(a+n+1)$
A: Assume that 
$$3^{2k+2}+56k+55=64m.$$
Then, use 
$$3^{2(k+1)+2}=3^{2k+4}=3^2\cdot 3^{2k+2}$$
and
$$3^{2k+2}=64m-56k-55.$$

$\begin{align}3^{2(k+1)+2}+56(k+1)+55&=9\cdot 3^{2k+2}+56k+56+55\\&=9(64m-56k-55)+56k+56+55\\&=9\cdot 64m-9\cdot 56k-9\cdot 55+56k+56+55\\&=9\cdot 64m-8\cdot 7\cdot 8k-6\cdot 64\\&=64(9m-7k-6)\end{align}$

A: Let $S(n)$ be the statement: $3^{2n+2}+56n+55$ is divisible by $64$; $n\geq0$
Basis step: $S(0)$:
$3^{2(0)+2}+56(0)+55=9+55$
$\hspace{37.25 mm}=64$, which is divisible by $64$
Inductive step:
Assume $S(k)$ is true, i.e. assume that $3^{2k+2}+56k+55$ is divisible by $64$; $k\geq0$
$\hspace{59 mm}\Rightarrow 3^{2k+2}+56k+55=64A$; $A\in{\mathbb{N}}$
$\hspace{59 mm}\Rightarrow 3^{2k+2}=64A-56k-55$
$S(k+1)$: $3^{2(k+1)+2}+56(k+1)+55$
$\hspace{12.5 mm}=3^{2k+2+2}+56k+111$
$\hspace{12.5 mm}=3^{2k+4}+56k+111$
$\hspace{12.5 mm}=3^{2}\bullet{3^{2k+2}+56k+111}$
$\hspace{12.5 mm}=9\bullet{3^{2k+2}+56k+111}$
$\hspace{12.5 mm}=9(64A-56k-55)+56k+111$
$\hspace{12.5 mm}=576A-504k-495+56k+111$
$\hspace{12.5 mm}=576A-448k-384$
$\hspace{12.5 mm}=64(9A-7k-6)$, which is divisible by $64$
So, $S(k+1)$ is true whenever $S(k)$ is true.
Therefore, $3^{2n+2}+56n+55$ is divisible by $64$; $n\geq0$.
A: Let $F(n) = 3^{(2n+2)} + 56n + 55$
Then $F(n+1) = 3^{(2(n+1)+2)} + 56(n+1) + 55$
Then we get:
$F(n+1) = 3^{(2n+4)} + 56n + 56 + 55 = \\
9.3^{(2n+2)} + (9.56.n - 8.56.n) + 56 + (9.55-8.55) = \\
(9.3^{(2n+2)} + 9.56.n + 9.55.n) - 8.56.n - 8.55 + 56 = \\
9.F(n) - 448.n - 384 = \\
9.F(n) - 64.7.n - 64.6$
Now from the last form of F(n+1) it's already obvious that: if 64/F(n) then 64/F(n+1).
And this is exactly the induction step you have to make to finalize your proof.   
In general: usually such problems are solved by expressing $F(n+1)$ in terms of $F(n)$. This way you can use the induction hypothesis (which you assume it's true). In our case that's the fact that $64 / F(n)$. And then what's left will be usually something which is obviously divisible by that number which they ask you to prove that it's divisible by (in our case that leftover is the value $64.7.n + 64.6$ which is obviously divisible by 64).    
