For all $n\in\Bbb N$ show $9\mid(16^n+12n-1)$

Question

This an exercise that I found in a maths book from the first lesson in the second year of high school called Logic. Here we have to demonstrate the proposition by reasoning with recurrences.

Show that for all $n\in\Bbb N$, $9\mid(16^n+12n-1)$.

I tried to solve this by recurrences but I keep getting false and illogical answers!

Answer 1

As regards 1), I guess that you would like to show that $9$ divides $16^n+12n-1$ for all $n\in\mathbb{N}$.

Hint. Try induction and note that $$16^{n+1}+12(n+1)-1=(18-2)16^{n}+(36-24)n+11\\ =18\cdot 16^n+36n+9-2(16^n+12n-1).$$

Answer 2

There is a standard method for (1). After checking the $n=0$ case, suppose the statement holds for $n$, that is $$ 16^n+12n-1=9t $$ for some integer $t$. This can also be written as $16^n=9t-12n+1$. Then \begin{align} 16^{n+1}+12(n+1)-1 &=16(9t-12n+1)+12n+11 \\ &=9\cdot 16t-15\cdot 12n+27 \\ &=9(16t-20n+3) \end{align}

I'll show another strategy for (2). You can subtract the expressions for the case $n$ from the one for the case $n+1$: \begin{align} (1+5^{n+2}+2\cdot3^{n+1})-(1+5^{n+1}+2\cdot3^{n}) &=5^{n+2}-5^{n+1}+2\cdot 3^{n+1}-2\cdot 3^{n}\\ &=4\cdot5^{n+1}-4\cdot3^n \\ &=4(5^{n+1}-3^n) \end{align} Since $5^{n+1}-3^n$ is even, you're done, because the afore mentioned difference is divisible by $8$. Since the case $n=0$ is true, this ends the proof.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

1. $\ds{ n = 9\left\lfloor{n \over 9}\right\rfloor + r_{n}\,,\ 16^{n} = 9\left\lfloor{16^{n} \over 9}\right\rfloor + s_{n}\,,\qquad\qquad \left\vert\ \begin{array}{rcl} && \ds{r_{n} \in \mathbb{N}_{\ \geq\ 0}\quad \mid\quad r_{n} < 9} \\[5mm] \ds{s_{n}} & \ds{=} & \left\{\begin{array}{ccrcl} \ds{1} & \mbox{if} & \ds{n} & \ds{=} & \ds{0} \\ \ds{7} & \mbox{if} & \ds{n} & \ds{=} & \ds{1} \\ \ds{4} & \mbox{if} & \ds{n} & \ds{=} & \ds{2} \\ \ds{s_{n - 3}} & \mbox{if} & \ds{n} & \ds{\geq} & \ds{3} \end{array}\right.\end{array}\right.}$

   ---

   \begin{align} 16^{n} + 12n - 1 & = \varepsilon + s_{n} + 3r_{n} - 1\quad\mbox{where}\quad 9 \mid \varepsilon \end{align}

   ---

   $\ds{s_{n} + 3r_{n} - 1}$ is periodic of period $\ds{9}$. Then, $\underline{\textit{it is sufficient}}$ to prove that $\ds{9 \mid \pars{s_{n} + 3n - 1}}$ for $\ds{n = 0, 1, 2,\ldots 8}$ which is quite trivial: $$ \begin{array}{cc}\hline \ds{n\quad} & \ds{\quad s_{n} + 3n - 1} \\ \hline \ds{0} & \ds{0} \\ \ds{1} & \ds{9} \\ \ds{2} & \ds{9} \\ \ds{3} & \ds{9} \\ \ds{4} & \ds{18} \\ \ds{5} & \ds{18} \\ \ds{6} & \ds{18} \\ \ds{7} & \ds{27} \\ \ds{8} & \ds{27} \\ \hline \end{array} $$

Question $\ds{\left.2\right)}$ follows a similar technique and question $\ds{\left.3\right)}$ is rather trivial.