Question

Use mathematical induction to prove that \(64\)divides

\({3^{2n + 2}} + 56n + 55\)for every positive integer \(n\).

Short answer

It is proved that\(64\)divides\({3^{2n + 2}} + 56n + 55\)for every positive integer n.

Step-by-step solution

Principle of Mathematical Induction

Consider the propositional function\(P\left( n \right)\). Consider two actions to prove that\(P\left( n \right)\)evaluates to accurate for all set of positive integers\(n\).

Consider the first basic step is to confirm that\(P\left( 1 \right)\)true.

Consider the inductive step is to demonstrate that for any positive integer k the conditional statement \(P\left( k \right) \to P\left( {k + 1} \right)\)is true.

Prove the basis step

Let\(P\left( n \right)\): “\(64\)divides\({3^{2n + 2}} + 56n + 55\)”

In the basis step, we need to prove that\(P\left( 1 \right)\)is true

For finding statement\(P\left( 1 \right)\)substituting\(1\)for\(n\)in the statement

\(\begin{aligned}{c}{3^{2n + 2}} + 56n + 55 &= {3^{2 + 2}} + 56 + 55\\ &= 81 + 56 + 55\\ &= 192\end{aligned}\)

\(192\)is divisible by\(64\).

From the above, we can see that the statement \(P\left( 1 \right)\) is true this is also known as the basis step of the proof.

Prove the Inductive step

In the inductive step, we need to prove that, if\(P\left( k \right)\)is true, then\(P\left( {k + 1} \right)\)is also true.

\(P\left( k \right) \to P\left( {k + 1} \right)\)is true for all positive integers k.

In the inductive hypothesis, one assumes that\(P\left( k \right)\)is true for any arbitrary positive integer\(k\).

\(64\)divides\({3^{2k + 2}} + 56k + 55\)

Now to show that\(P\left( {k + 1} \right)\)is also true replace\(k\)with\(k + 1\)in the statement

\(\begin{aligned}{c}{3^{2\left( {k + 1} \right) + 2}} + 56\left( {k + 1} \right) + 55 &= {3^2} \cdot {3^{2k + 2}} + 56k + 56 + 55\\ &= 9 \cdot {3^{2k + 2}} + 56k + 56 + 55\\ &= {3^{2k + 2}} + 56k + 55 + 8 \cdot {3^{2k + 2}} + 56\\ &= {3^{2k + 2}} + 56k + 55 + 8 \cdot \left( {{3^{2k + 2}} + 7} \right)\end{aligned}\)

The first term of the expression is divisible by 64 from the inductive hypothesis and second term is divisible by 8.

Now we need to show\({3^{2k + 2}} + 7\)is divisible by 8.

For, Basis step

\(\begin{aligned}{l}k &= 1\\{3^{2 + 2}} + 7 &= 88\end{aligned}\)

Consider the expression is divisible by 8. Solve by inductive step as:

\(\begin{array}{c}k \to k + 1\\{3^{2\left( {k + 1} \right) + 2}} + 7 = {9.3^{2k + 2}} + 7\\ = {3^{2k + 2}} + 7 + {8.3^{2k + 2}}\end{array}\)

The first term of the expression is divisible by 8 and second term is divisible by 8

So, it is divisible by 8

Therefore, now both the terms in the expression of\({3^{2\left( {k + 1} \right) + 2}} + 56\left( {k + 1} \right) + 55\)are divisible by 64, So we conclude\({3^{2\left( {k + 1} \right) + 2}} + 56\left( {k + 1} \right) + 55\)is divisible by 64

From the above it is clear that\(P\left( {k + 1} \right)\)is also true.

Hence,\(P\left( {k + 1} \right)\)is true under the assumption that\(P\left( k \right)\)is true. This

completes the inductive step.

Hence it is proved that “\(64\)divides\({3^{2n + 2}} + 56n + 55\)for every positive integer n.