Proving that $64$ divides $3^{2n+2}+56n+55$ by induction

Question

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.

Answer 1

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).

Answer 2

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}$

Answer 3

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$

Answer 4

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$

Answer 5

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)$

Answer 6

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$.

Answer 7

Proof by induction.

Let P(n) denote the proposition: "3²ⁿ⁺²+56n+55 is divisible by 64"

Basis step:

P(0) is true because 3²⁽⁰⁾⁺²+56(0)+55= 64. This completes the basis step.

Inductive step:

Assume that P(k) is true for an arbitrary non-negative integer k, that is, we assume that 3^2k+2+56k+55 is divisible by 64 (inductive hypothesis). Now, we must show that if we assume that P(k) is true then P(k+1) is also true.

Note that P(k+1) = 3^2(k+1)+2+56(k+1)+55

->3^2k+4+56k+56+55

->3²*3^2k+2+56k+56+55 (By basic algebra we know that 3^2k+4=3²*3^2k+2)

->9*3^2k+2+56k+56+55

->8*3^2k+2+3^2k+2+56k+56+55 (By basic algebra we know that  9*3^2k+2=8*3^2k+2+3^2k+2)

->8(3^2k+2+7)+3^2k+2+56k+55 (Factoring the first and fourth term)

->8(3^2k+2+56k-56k+55-48)+3^2k+2+56k+55 (Equal to the above expression)

->8(3^2k+2+56k+55-8(7k+6))+3^2k+2+56k+55 (Factoring -56k and -48)

->8(3^2k+2+56k+55)-64(7k+6)+3^2k+2+56k+55 (Equal to the above expression)

->9(3^2k+2+56k+55)-64(7k+6)

Resulting expression: ->9(3^2k+2+56k+55)-64(7k+6)

Using the inductive hypothesis, we conclude that the above expression is divisible by 64.