Prove $\frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$ by induction

Question

Here is my attempted proof:

$\forall n \in \mathbb{N}$, let $S_n$ be the statement: $\frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$

Base case: $S_1$: $\frac{2^{4(1)}-(-1)^1}{17} = \frac{16+1}{17} = 1 \in \mathbb{N}$

Inductive step: $\forall n \geq 1$, $S_n$ holds

$S_{n+1}$: $\frac{2^{4(n+1)}-(-1)^{n+1}}{17} = \frac{2^{4n} \cdot 2^4 +(-1)^{n}}{17} = \frac{2^{4n} \cdot (2^4+1) - 2^{4n} +(-1)^{n}}{17}$.

Now, we are left with $2^{4n} - \frac{2^{4n}-(-1)^n}{17}$.

We know $\frac{2^{4n}-(-1)^n}{17}$, $2^{4n} \in \mathbb{N}$ and $2^{4n} > \frac{2^{4n}-(-1)^n}{17} \implies 2^{4n} - \frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$

$$\tag*{$\blacksquare$}$$

Is my proof correct? I also feel there is a more elegant/smoother proof (assuming mine is correct).

Answer 1

Your proof is fine.

But note:

$(a - b)(\sum\limits_{k=0}^{n-1} a^kb^{n-1 -k}) =$

$a(\sum\limits_{k=0}^{n-1} a^kb^{n-1 -k}) - (\sum\limits_{k=0}^{n-1} a^kb^{n-1 -k})=$

$(\sum\limits_{k=0}^{n-1}a^{k+1}b^{n-1 - k}) -(\sum\limits_{k=0}^{n-1}a^kb^{n-k}) = $

$(\sum\limits_{j=1}^n a^jb^{n-j})-(\sum\limits_{j=0}^{n-1}a^jb^{n-j})=$

$([\sum\limits_{j=1}^{n-1} a^jb^{n-j}]+a^nb^{n-n}) - (a^0b^{n-0}+[\sum\limits_{j=1}^{n-1} a^jb^{n-j}]) = $

$a^n - b^n$.

So for all integers $a,b$ and $n\ge 1$ we will always have $a-b$ divides $a^n - b^n$

So $2^4 -(-1) = 17$ will always divide $(2^4)^n - (-1)^n$.

Answer 2

Yes. Conceptually the induction follows very simply by multiplying the congruences below using CPR = Congruence Product Rule, $ $ i.e. raise $\ 16\equiv\, -1\ $ to the power $n$ by inductively multiplying

$$\begin{align}\bmod 17\!:\qquad \color{#c00}{16}\ &\equiv\ \color{#c00}{{-}1}\\ 16^{\large n}&\equiv (-1)^{\large n}\qquad\quad\ P(n)\\ \Rightarrow\ \ \color{#c00}{16}\,16^{\large n}&\equiv (-1)^{\large n}(\color{#c00}{-1})\quad\ P(n\!+\!1)\end{align}\quad\ \ \ $$

i.e. the proof is a special case of the (inductive) proof of the Congruence Power Rule.. Thus the use of congruences has highlighted innate arithmetical structure allowing us to reduce the induction to an easy one $\,a\equiv b\,\Rightarrow\, a^n\equiv b^n,\,$ with obvious inductive step: multiply by $\,a\equiv b\,$ via the product rule.

If you don't know congruences we can preserve this arithmetical essence by using an analogous product rule for divisibility, with $\ m\mid n\ $ meaning $\,m\,$ divides $\,n,\,$ namely

$$\qquad\ \begin {align} &17\mid\ \color{#c00}{16\,\ \ -\ \ B}\qquad\quad\ \ [B = -1\,\ {\rm in\ OP}]\\ &17\mid\ \ \ \ \ 16^{\large n} -\ B^{\large n}\qquad\ P(n)\\ \Rightarrow\ \ &17\mid\ \color{#c00}{16}16^{n}\! -\!\color{#c00}BB^{\large n}\qquad\ P(n\!+\!1) \end{align} $$

$\begin{align}{\bf Divisibility\ Product\ Rule}\ \ \ \ &m\mid\ a\ -\ b\qquad {\rm i.e.}\quad \ a\,\equiv\, b\\ &m\mid \ \ A\: -\: B\qquad\qquad \ A\,\equiv\, B\\ \Rightarrow\ \ &\color{}{m\mid aA - bB}\quad \Rightarrow\quad aA\equiv bB\!\pmod{\!m}\\[.2em] {\bf Proof}\,\ \ m\mid (\color{#0a0}{a\!-\!b})A + b(\color{#0a0}{A\!-\!B}) &\,=\, aA-bB\ \ \text{by $\,m\,$ divides $\rm\color{#0a0}{green}$ terms by hypothesis.}\end{align}$

You can find further discussion in many prior posts.

Answer 3

Alternatively, assuming $\frac{2^{4n}-(-1)^n}{17} \in \mathbb{N}$: $$\begin{align}\frac{2^{4(n+1)}-(-1)^{n+1}}{17} &= \frac{2^{4n} \cdot 2^4 +(-1)^{n}}{17} =\\ &=\frac{2^{4} \cdot (2^{4n}-(-1)^n) + 2^{4}(-1)^n +(-1)^{n}}{17}=\\ &=2^4\cdot \underbrace{\frac{2^{4n}-(-1)^n}{17}}_{\ge 1}+(-1)^{n}\in \mathbb N. \end{align}$$