My Math Forum Induction again

 Algebra Pre-Algebra and Basic Algebra Math Forum

 April 8th, 2014, 03:11 AM #1 Senior Member     Joined: Oct 2013 From: Far far away Posts: 429 Thanks: 18 Induction again Prove that (4^n) - 1 is divisible by 3 My attempt: 1) let n = 1 (4^1) - 1 = 4 - 1 = 3 3 is divisible by 3. So true for n = 1 2) Assume it is true for n = k So (4^k) - 1 is divisible by 3 3) let n = k + 1 $4^{k+1}-1=(4^k)(4)-1=(4^k)(3+1)-1=3(4^k)+[4^k+1]$ but $3(4^k)$ and $4^k+1$ are divisible by 3 so $4^{k+1}$ is divisible by 3 Therefore for all n 4^n - 1 is divisible by 3 Is this proof acceptable? The third step doesn't look like induction..thanks
April 8th, 2014, 03:19 AM   #2
Senior Member

Joined: Dec 2013
From: Russia

Posts: 327
Thanks: 108

Quote:
 Originally Posted by shunya 3) let n = k + 1 $4^{k+1}-1=(4^k)(4)-1=(4^k)(3+1)-1=3(4^k)+[4^k+1]$ but $3(4^k)$ and $4^k+1$ are divisible by 3
$4^k+1$ should be replaces by $4^k-1$ (two times). Otherwise, the proof is correct. For clarity, it would be nice to say that $3\mid(4^k-1)$ by induction hypothesis.

 Tags induction

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post shunya Algebra 2 April 8th, 2014 03:27 AM cool012 Algebra 0 December 1st, 2013 05:37 AM tejolson Linear Algebra 2 February 20th, 2013 10:38 AM OriaG Algebra 11 October 27th, 2012 03:55 PM gaussrelatz Algebra 4 September 28th, 2011 08:55 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top