Use Mathematical Induction to Prove $ 7^{n+2} + 8^{2n+1}$ is Divisible by 57 for every Nonnegative Integer $n$

Question

I can see the answer to this in my textbook; however, I am not quite sure how to solve this for myself . . . the book has the following:

To take advantage of the inductive hypothesis, we use these steps:

$ 7^{(k+1)+2} + 8^{2(k+1)+1} = 7^{k+3} + 8^{2k+3} $

$$ = 7\cdot7^{k+2} + 8^{2}\cdot8^{2k+1}\\ = 7\cdot7^{k+2} + 64\cdot8^{2k+1}\\ = 7(7^{k+2}+8^{2k+1})+57\cdot8^{2k+1}\\ $$

While the answer is apparent to me now; how exactly would I go about figuring out a similar algebraic manipulation if I were to see something like this on a test? Is there an algorithm or a way of thinking about how to break this down that I'm missing? I think I'm most lost regarding the move from the second to last and last equations.

Source: Discrete Mathematics and its Applications (7th ed), Kenneth H. Rosen (p.322)

Answer 1

I don't think there is an algorithm for that, but I'd start by simplifying $$ 7^{n+2} + 8^{2n+1} = 49\cdot 7^n + 8 \cdot 64^n $$ Now note that $49+8=57$ and $64-7=57$, which at least suggests where $57$ comes from.

This observation is probably useful if you write $64^n=(57+7)^n$ and use the binomial theorem.

Answer 2

The steps to the third line seem routine, trying to find the terms of the inductive hypothesis. Once you are at the third line you have to decide to split the $64$ into $7+57$. You might just notice that both numbers are important in the problem and try it. You might notice that splitting out $7$ of the second term is what is needed to complete the inductive hypothesis in the first term, so try it. When you see $57$ is left you should be convinced that is the right track.

Answer 3

"..for every non-negative integer $n$" means that it shall be valid starting from $n=0$.
In fact $F(0)= 7^2+8=57$.

You already found that $F(n+1)=7 \,F(n)+57\,8^{2n+1}$ which is clearly divisible by 57.
So $$57\backslash F(n)\quad \left| {\;0 \le n} \right.$$

Answer 4

By the Chinese remainder theorem something is $\equiv 0\pmod{57}$ iff it is $\equiv 0\pmod{3}$ and $\equiv 0\pmod{19}$. On the other hand $$ a_n = 7^{n+2}+8^{2n+1} = 49\cdot 7^n + 8\cdot 64^n $$ fulfills $$ a_n \equiv 49\cdot 1^n+8\cdot 1^n \equiv 57 \equiv 0\pmod{3} $$ $$ a_n \equiv 49\cdot 7^n+8\cdot 7^n \equiv (-8+8)7^n \equiv 0\pmod{19} $$ hence you do not need induction.

Answer 5

you would have to think about how to get the form desired. in this case the first part of:

$7(7^{k+2}+8^{2k+1})+57⋅8^{2k+1}$

We have made a factor, of the form desired. Assuming it's divisible by 57, that part of the sum is, and the other part shows it is already. So, the sum of both parts, must divide by 57. Hence, the original number must divide by 57. The original number is of the form suggested but with n replaced by k+1. so it must be true for n=k+1, assuming it works for n=k. then what's left this to show it works for some base value of k. As $7^3+8^3=343+512=855=57\cdot {15}$ it works for n=k=1, and it follows by what we've shown that it then works for all k>1 . edit: okay I forgot the 0 case ( see G cab's answer): as 49+8=57, we also have it for the k=0 case, and again all other cases are shown by induction.

Answer 6

The key is to get very clear on what you have, and what you want.

For the inductive step, you have the inductive assumption:

$7^{k+2}+8^{2k+1}$ is divisible by $57$

And you want to show that:

$7^{(k+1)+2}+8^{2(k+1)+1}$ is divisible by $57$

So, you should think to yourself: OK, I want to show that $7^{(k+1)+2}+8^{2(k+1)+1}$ is divisible by $57$, and of course at some point I want to use my inductive hypothesis that $7^{k+2}+8^{2k+1}$ is divisible by $57$ to help me with this. So: I probably want to manipulate/rewrite the expression $7^{(k+1)+2}+8^{2(k+1)+1}$ so that I get some term $7^{k+2}+8^{2k+1}$ in there. How can I do that? Well, I have $1$ extra $7$ in the $7^{(k+1)+2}$ term, and I have $2$ extra $8$'s in the $8^{2k+1}$ term, so I should pull those out:

$$7^{(k+1)+2}+8^{2(k+1)+1} =$$

$$7^{(k+2)+1}+8^{(2k+1)+2} =$$

$$7\cdot 7^{k+2}+8^2\cdot 8^{2k+1}=$$

$$7\cdot 7^{k+2}+64\cdot 8^{2k+1}$$

Now, it is not quite clear yet how to isolate a $7^{k+2}+8^{2k+1}$, but at this point you might notice something: we got a 7 ... and we got a 64 ... the difference of which is 57 (!). Hmmm.... OK, let's try this:

$$7\cdot 7^{k+2}+64\cdot 8^{2k+1}=$$

$$7\cdot 7^{k+2}+(57+7)\cdot 8^{2k+1}=$$

$$7\cdot 7^{k+2}+57\cdot 8^{2k+1}+7\cdot 8^{2k+1}=$$

(and at this point you'll see it ...)

$$57\cdot 8^{2k+1}+7\cdot 7^{k+2}+ 7\cdot 8^{2k+1}=$$

$$57\cdot 8^{2k+1}+7\cdot (7^{k+2}+ 8^{2k+1})$$

The term $57\cdot 8^{2k+1}$ is clearly divisible by $57$, and we just isolated the $7^{k+2}+ 8^{2k+1}$ for the second term, so that is divisble by $57$ as well, meaning that their sum is divisible by $57$ as well.

Answer 7

\begin{align} 7^{n+2}+8^{2n+1}&=49\cdot 7^n+8\cdot 64^n \\ &\equiv -8\cdot 7^n+8\cdot 7^n\equiv 0\bmod{57}. \end{align}

Answer 8

Hint $ $ To induct simply multiply the first two congruences below (by the Congruence Product Rule)

$$\begin{align} \bmod 57\!:\qquad\ \ 7&\equiv 8^{\large 2}\\[.3em] {-}7^{\large n+2}&\equiv 8^{\large 2n+1}\ \ \ {\rm i.e.}\ \ P(n)\\ \overset{\rm multiply}\Longrightarrow\ {-}7^{\large n+3} &\equiv 8^{\large 2n+3}\ \ \ {\rm i.e.}\ \ P(n\!+\!1) \end{align}$$

Remark $ $ Just as above, the arithmetical essence of many inductive proofs is greatly clarified using congruence language. In fact we can make it clearer by showing that the induction amounts to raising $\,7\equiv 8^2$ to power $n,\,$ using the Congruence Power Rule, then multiplying the result by the base-case congruence $\,-7^2\equiv 8,\,$ using the Congruence Product Rule, $ $ i.e.

$$\qquad \qquad\qquad \begin{align} \bmod 57\!:\quad {-}7^2&\equiv 8\qquad\quad\ \rm [Base\ Case]\\[.3em] 7^{\large n}&\equiv 8^{\large 2n}\ \ \ {\rm by}\ \ [7\equiv 8^{\large 2}]^{\large n}\ \ {\rm by\ \ Power\ Rule}\\ \overset{\rm multiply}\Longrightarrow\ {-}7^{\large n+2} &\equiv 8^{\large 2n+1} \end{align}$$

Thus we see that the arithmetical essence of the induction on $\,n\,$ amounts to the fact that congruences are preserved under raising to power $\,n,\,$ whose inductive proof has been abstractly encapsulated into a conveniently reusable lemma, the Congruence Power Rule. Once we are familiar with this inductive pattern, we can easily recognize when it occurs in future inductions, eliminating the often difficult meandering search for the key idea for the inductive step.

Furthermore, using the above viewpoint we can mechanically generate the proof in your book, e.g. see this answer where I do that explicitly for two proofs. However, we should not aim to derive proofs that obfuscate the (arithmetical) essence of the matter. Rather, we should aim to derive proofs that highlight the essence - as above.