Proof by Induction: Solving 34n-1 Divisible by 80

[Damo]

As a student, proofs always troubled me, now as a teacher they are still causing me grief.
How would you do this one?

Prove 3⁴ⁿ - 1 is divisible by 80.

I understand the process, setting the base and writing as n=k, then n=k+1 etc. But this has stumped me.

 

[MarkFL]

Try adding:

$$\left(3^{4(n+1)}-1\right)-\left(3^{4n}-1\right)=80\cdot3^{4n}$$

to your induction hypothesis. :D

 

[Fallen Angel]

Hi,

$80=2^4 5$, so you need to check that $3^{4n}-1$ is zero modulo 16 and zero modulo 5 for every $n$.

$3^4=81 \equiv 1 \ (mod \ 16)$ so $3^{4n}\equiv 1 \ (mod \ 16)$.

$3^4=81 \equiv 1 \ (mod \ 5)$ so $3^{4n}\equiv 1 \ (mod \ 5)$.

so it must be divisible by 80.

PS: MarkFL was faster =P

 

[Nono713]

Or even more directly:
$$3^{4n} - 1 \equiv \left ( 3^{4} \right )^n - 1 \equiv 81^n - 1 \equiv 1^n - 1 \equiv 1 - 1 \equiv 0 \pmod{80}$$
Alternative proof:
$$3^{4n} - 1 = \left ( 3^{4} \right )^n - 1 = 81^n - 1 = 80 \left ( 81^{n - 1} + 81^{n - 2} + \cdots + 1 \right )$$
Of course, neither uses induction, but still.

 

[Damo]

Try adding:

$$\left(3^{4(n+1)}-1\right)-\left(3^{4n}-1\right)=80\cdot3^{4n}$$

to your induction hypothesis. :D

I understand the Left hand side of this equation but where/why is the right hand side $$80\cdot3^{4n}$$?

 

[MarkFL]

I understand the Left hand side of this equation but where/why is the right hand side $$80\cdot3^{4n}$$?

If follows by simplification:

$$\left(3^{4(n+1)}-1\right)-\left(3^{4n}-1\right)=3^{4(n+1)}-3^{4n}=3^{4n+4}-3^{4n}=81\cdot3^{4n}-3^{4n}=80\cdot3^{4n}$$

 

[Damo]

Thank you guys for your responses. I think I have it now and will now work on how to communicate it to my students. We are doing a brief intro to mathematical induction in class on Thursday and I was feeling underprepared!

Thanks for your help!