[Math] 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.

Best Answer


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$

Related Question