1
$\begingroup$

For all $n\ge1$, use mathematical induction to establish each other the following divisibility statements: $$5\mid2^{4n}-1$$

I was wondering if someone could help me with the set up of this proof. I only have done proofs with mathematical induction when I am given a series of numbers and I can incorporate my induction hypothesis in for one of my terms in the series.

Step by step explanation please?

$\endgroup$
  • 1
    $\begingroup$ I know the question asks for an induction, but I don't think we have to use the induction, by the way: $2^{4n}-1=(2^4-1)((2^4)^{n-1}+\cdots+1).$ $\endgroup$ – awllower Feb 9 '14 at 6:53
3
$\begingroup$

Since you're new to induction, I'll give the framework and let you fill in the details. The induction step goes something like this:

Suppose that $5| 2^{4n} - 1$, and write $5k = 2^{4n} - 1$. Then

\begin{align*} 2^{4(n + 1)} - 1 &= 2^{4n} \cdot 2^4 - 1 \\ &= (5k + 1) \cdot 16 - 1 \\ &= 5k + 16 - 1 \end{align*}

Can you finish it from here, justifying each step?

$\endgroup$
  • $\begingroup$ why did you substitute (5k+1)?? wouldn't (2^4n)-1 all just be replaced with 5k? $\endgroup$ – Lil Feb 10 '14 at 23:30
  • $\begingroup$ @Lil I am replacing $2^{4n}$ only. $\endgroup$ – user61527 Feb 10 '14 at 23:31
1
$\begingroup$

Since you asked for a set-up,

  1. Show the statement is true for $n=1$, i.e.

$$5 \ \Big| \ 2^4-1$$

  1. Let $n\in\mathbb{N}$ be fixed. Assume for all $k<n$ that

$$5 \ \Big| \ 2^{4k}-1$$

Show that

$$5 \ \Big| \ 2^{4n}-1$$

$\endgroup$
1
$\begingroup$

If $\displaystyle F(k)=2^{4k}-1,$

$\displaystyle F(k+1)-2^4\cdot F(k)=2^{4(k+1)}-1-2^4[2^{4k}-1]=2^4-1=15$

$\displaystyle\implies F(k+1)$ will be divisible by $15,$ (hence by $5$) if $F(k)$ is

Now establish the base case i.e., $k=0$

$\endgroup$
1
$\begingroup$

Hint $\ $ Let $\,f_n = 2^{4n}\!-1$. Prove the base case $\,5\mid f_0.\,$ Next prove $\,5\mid \color{#0a0}{f_{n+1}\!-f_n},\,$ therefore $\,5\mid \color{#c00}{f_n}\,\Rightarrow\, 5\mid \color{#0a0}{f_{n+1}\!-f_n}+\color{#c00}{f_n} = f_{n+1},\ $ i.e. $\ 5\mid f_n\,\Rightarrow\,5\mid f_{n+1} \,$ (the induction step).

Remark $\ $ Unwinding the above telescopic cancellation we can write $\,f_n\,$ as the sum of its differences $\ f_{k+1}-f_k = (16-1) 16^k$ which yields the following simple proof

$$ 5\mid 16-1\,\Rightarrow\, 5\mid 16^{n}-1\, =\, (16-1)\,(16^{n-1}+\cdots + 16^2 + 16 + 1)$$

See my posts on telescopy for many more examples

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.