Induction: Divisibility Proof example 3 (4^n - 1 is divisible by 3)

[japanfan]

It's been 2 years I've seen the proof for a classical example of inductive proof, but never have I thought of resolving it somewhat by applying just one transformation instead of two.
If the exercise was to prove that a^k - 1 is a multiple of a-1, during the heredity step, I'd have multiplied the assumption equation by a to increment the exponent on 4 and added a-1 to retrieve the -1 addend, which is indeed a bit longer.
That might come in handy if I were to teach maths someday (well, hoping it will work ^^). Thank you for what constitutes a discovery to me :)

[drewprof]

Love the enthusiasm, well done Eddie!

[TURTWIG]

Eddie you are an amazing teacher you should see our lecturer at university so terrible

[dectectivetrash-can]

Algebraically, a^n - b^n is perfectly divisible by a - b

[salmona]

Hi, your videos have been VERY helpful!! Would you be able to do a video on Induction where it's divisible by all positive odd or even integers? Thanks!

[banjonpro]

A really easy way to prove this is to convert 4^k - 1 = 3P (original assumption) to 4^k = 3P + 1.

Then, in the second assumption (4*4^k - 1 = 3Q) just plug in the 3P + 1 we got before. That leaves the second assumption as:

4*(3P + 1) - 1 = 3Q

which can be rewritten as:

12P + 3 = 3Q

and we are done.

[alfyalex]

I have a question. At 3:48 he says it’s “the next case over”. So logically shouldn’t we choose 3(p+1) instead of 3Q?

[mohijitsingh]

4^k - 1=3P
4(4^k - 1)= 4 x 3P
4^(k+1) - 4 = 12P

Add 3 on both sides,
4^(k+1) - 1 = 12P+3= 3(4P+1)

[DANIELARAUJO-wo]

and the case 3^n|4^3^n-1 - 1 for all n for mathematical induction?

[sleepingsaucer]

I feel a bit disheartened. Yesterday, I was jumping up and down in our house being so joyful for finding a proof that 2^2x - 1 (or 4^x - 1) is divisible by 3 (High School student). I've used factorization, and used a number line to prove it. I thought that was so cool until I saw this video that shows a much cleaner and more legitimate proof. :'(
A question though, can this proof be able to help prove the Collatz conjecture?

[angelina]

I still quite not understand how you broke the 5.5^k -1

[therealg]

Hi, I thought that you have to manipulate P(n+1) follows from P(n), that is by mathematical induction show that for all n in some domain, P(n) -> P(n+1). So following from P(n), couldn't you have rearranged P(n) to get 4^k = 3P - 1, then multiply by 4 to get, 4^(k+1) = 12P - 4 = 3(4P+1), so 4^(k+1)-1 = 3(4P+1)? So by mathematical induction, P(n+1) follows from P(n).

[gabriele]

well done Eddie. the test should start 0 because 4^0 -1=0 and 0 is a multiple of any number since 3x0=0 ;)

[abhilashbarigidad]

Hey, here is just another method to prove 4^n-1 to be divisible by 3.

4^n-1={1+(4-1)}^n-1
       =1+nC1*(4-1)^1+ nC2*(4-1)^2 -1
       =nC1*(4-1)^1+ nC2*(4-1)^2
     
Hence, it can be seen that (4-1)^n is divisible by 3. Hope this is useful. Just another way of proving it by binomial.

[peterhyland]

An alternative proof: 4 = 1 mod3 :. 4^n = 1^n mod3 = 1 mod3 iff n is a non-negative whole number => 4^n – 1 = (1-1)mod3 = 0 mod3. Thus, 3 divides 4^n – 1 iff 4^n - 1 >= 3 so, n >= 1. This proves the result for 1, 2, 3... QED.