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

  • Thread starter Thread starter Damo
  • Start date Start date
  • Tags Tags
    Induction Proof
AI Thread Summary
The discussion focuses on proving that 34n - 1 is divisible by 80 using mathematical induction. Participants emphasize the importance of checking the expression modulo 16 and modulo 5, demonstrating that 3^4 is congruent to 1 in both cases. An alternative proof is provided, showing that 3^(4n) - 1 can be expressed as a product involving 80. The right-hand side of the equation in the induction hypothesis is clarified through simplification. The original poster expresses gratitude for the assistance and feels better prepared to teach the concept.
Damo
Messages
4
Reaction score
0
As a student, proofs always troubled me, now as a teacher they are still causing me grief.
How would you do this one?

Prove 34n - 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.
 
Physics news on Phys.org
Try adding:

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

to your induction hypothesis. :D
 
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
 
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.
 
MarkFL said:
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}$$?
 
Damo said:
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}$$
 
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!
 
Back
Top