# Thread: problem to prove based on mathematical induction

1. ## problem to prove based on mathematical induction

prove that (2 pow n . 2 pow n) - 1 is divisible by 3 by mathematical induction.

2. Originally Posted by sudeepmansh

prove that (2 pow n . 2 pow n) - 1 is divisible by 3 by mathematical induction.
Where are you having trouble?

3. base step: n=0 : ( 2 pow 0 . 2 pow 0) - 1 = 0 is divisible by 3. so the stmt is true for n=0.

inductive step: let us assume that the statement is true for any value of n. Now we have to prove that the stmt is true for n = n+1.

(2 pow n+1 . 2 pow n+1 ) - 1
2 pow (2n+2) - 1

how to solve after this step. I am struck here....

4. Originally Posted by sudeepmansh
base step: n=0 : ( 2 pow 0 . 2 pow 0) - 1 = 0 is divisible by 3. so the stmt is true for n=0.

inductive step: let us assume that the statement is true for any value of n. Now we have to prove that the stmt is true for n = n+1.

(2 pow n+1 . 2 pow n+1 ) - 1
2 pow (2n+2) - 1

how to solve after this step. I am struck here....
Note that $2^{2(k+1)} - 1 = 2^{2k} \cdot 4 - 1 = 4 \left( 2^{2k} - 1\right) + 3$.