Prove by induction?

The problem asks to prove $8^{(n+2)}+9^{(2n+1)}$ is divisible by 73

Proof by induction:

we look at base case $n=1$ => which gives us $1241$ which is divisible by $73$; now for $n+k$

we know that $8^{(k+2)}+9^{(2k+1)}=73t$ for some integer $t$ then $$8^{(k+3)}+9^{(2k+3)}=8\cdot 8^{(k+2)}+81\cdot 9^{(2k+1)}$$

I am stuck on this step. I want to get $8^{(k+2)}+9^{(2k+1)}$ together so i can change them into $73t$ but dont know how to do it, or am i over thinking all of this.

-

You don't have to be clever, just comfortable with induction.

Suppose $73 | 8^{n+2}+9^{2n+1}$ ("$|$" means "divides exactly").

Putting $n+1$ for $n$, you want to show that this implies that $73 | 8^{n+3}+9^{2n+3}$ .

This will be true if $73$ divides their difference, which is $8^{n+3}+9^{2n+3}-(8^{n+2}+9^{2n+1})$.

Working this out, this is

$\begin{array} ( 8^{n+3}+9^{2n+3}-(8^{n+2}+9^{2n+1}) &=(8^{n+3}-8^{n+2}) +(9^{2n+3}-9^{2n+1})\\ &=8^{n+2}(8-1) +9^{2n+1}(9^2-1)\\ &=7 \cdot 8^{n+2} +80\cdot 9^{2n+1}\\ &=7 \cdot 8^{n+2} +(73+7)\cdot 9^{2n+1}\\ &=7 \cdot (8^{n+2}+9^{2n+1}) +73\cdot 9^{2n+1}\\ \end{array}$

By the induction assumption, $73 | 8^{n+2}+9^{2n+1}$, so $73$ divides this sum, and therefore divides $8^{n+3}+9^{2n+3}$.

I worked this out as I went along, and the only thing that might be considered "clever" is noticing that $80 = 73+7$. I guess that I "had" to do something at that point, because otherwise I would have been stuck. This also forced the induction hypothesis to come into play here. I find this interesting because it is used twice, once in computing the difference, and once in showing that the difference is divisible by 73.

It might be interesting to try to generalize this, because this kind of thing is rarely a coincidence.

-

This can be done in various ways:

$$8\cdot 8^{k+2}+81\cdot 9^{2k+1}=8\cdot(8^{k+2}+9^{2k+1})+?$$ is one example.

Note also that any sequence of the form $a_n=r\cdot 8^n+s\cdot81^n$ satisfies a recurrence relation i.e. $$a_{n+2}-(8+81)a_{n+1}+8\cdot 81 a_n=0$$ where you can see how the coefficients are made up. Then you need two cases to get started, but it is obvious that divisibility persists.

-
Note that both these forms essentially rely on the trick Cameron Williams notes. –  Mark Bennet Mar 23 '14 at 21:50

Hint: Try adding and subtracting $8\cdot 9^{2k+1}$ (or $81\cdot 8^{k+2}$) and see what happens. The reason for doing this is that, as written, we can't immediately invoke the inductive hypothesis but if we introduce either of these terms, we would get exactly what we want.

-
Would someone care to explain why my post has been marked for deletion? In Lay's book, this is exactly what he does for these kinds of problems. –  Cameron Williams Mar 23 '14 at 21:46

Since we know by the induction hypothesis that: $$8^{k+2} + 9^{2k+1} = 73t$$ for some $t \in \mathbb Z$, try solving for one of the powers and substituting. For example, solving for the second power yields $9^{2k+1} = 73t - 8^{k+2}$ so that: \begin{align*} 8[8^{k+2}]+81[9^{2k+1}] &= 8[8^{k+2}]+81[73t - 8^{k+2}] \\ &= 8[8^{k+2}]+81[73t] - 81[8^{k+2}] \\ &= 81[73t] - 73[8^{k+2}] \\ &= 73\underbrace{[81t - 8^{k+2}]}_{\in ~\mathbb Z} \\ \end{align*}

-

$\begin{eqnarray}{\bf Hint}\,\ \ {\rm mod}\ 73\!: &&\quad\, 8\ \equiv\ 9^2\\ {\rm times} \ &&8^{n+2}\equiv - 9^{2n+1}\\ \Rightarrow\ \ &&8^{n+3}\equiv -9^{2n+3}\ \ \text{is the induction step.} \end{eqnarray}$

-
This method generalizes widely, see this answer. –  Bill Dubuque Mar 24 '14 at 4:33

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ \begin{align} \color{#00f}{\large 8^{n + 2} + 9^{2n + 1}}&=64 \times 8^{n} + 9\times 81^{n} =73 \times 8^{n} + 9\pars{81^{n} - 8^{n}} \\[3mm]&=73 \times 8^{n} + 9\pars{81 - 8}\sum_{j = 0}^{n - 1}81^{n - j - 1}8^{j} =\color{#00f}{\Large 73}\bracks{8^{n} + 9\sum_{j = 0}^{n - 1}81^{n - j - 1}8^{j}} \end{align}

-