Induction: Prove 2^(2n) - 1 divisible by 3 for all n >= 1

flakine

Junior Member
Joined
Aug 24, 2005
Messages
78
Prove that 22n1 is divisible by 3,  integers n1\displaystyle \text{Prove that }2^{2n} - 1\text{ is divisible by 3, }\forall \text{ integers n} \geqslant \text{1}

Show p(a) [’a’ is min value of statement]\displaystyle \text{Show p(a) ['a' is min value of statement]}
3|22(1)1\displaystyle \text{3|2}^{\text{2(1)}} - 1
 221=3(i) [i is an integer]\displaystyle \text{ }2^2 - 1 = 3(i)\text{ }[i\text{ is an integer]}
3 = 3(i)\displaystyle \text{3 = 3}(i)

Suppose p(k) k = n\displaystyle \text{Suppose p(k) k = n}
22k1=3(i) [inductive step]\displaystyle 2^{2k} - 1 = 3(i)\text{ }[\text{inductive step]}

We wish to show p(k + 1) \displaystyle \text{We wish to show p(k + 1) }
22(k+1)1=3(i) \displaystyle 2^{2(k + 1)} - 1 = 3(i)\text{ }

 [starting on left hand side]\displaystyle \text{ [starting on left hand side]}

22(k+1)1=22k+21\displaystyle 2^{2(k + 1)} - 1 = 2^{2k + 2} - 1

 = 2222k1\displaystyle \text{ = 2}^\text{2} 2^{2k} - 1

 = 22k41\displaystyle \text{ = }2^{2k} \bullet 4 - 1

 = ??????? \displaystyle \text{ = ??????? }

How do I get there from here, please provide your reasoning. Thanks!\displaystyle \text{How do I get there from here, please provide your reasoning}\text{. Thanks!}
 
You're gonna kick yourself, you were so close! :wink:

. . . . .4(2[sup:2zqj5hxp]2k[/sup:2zqj5hxp]) - 1

. . . . .3(2[sup:2zqj5hxp]2k[/sup:2zqj5hxp]) + 1(2[sup:2zqj5hxp]2k[/sup:2zqj5hxp]) - 1

. . . . .3(2[sup:2zqj5hxp]2k[/sup:2zqj5hxp]) + [2[sup:2zqj5hxp]2k[/sup:2zqj5hxp] - 1]

The first term is obviously divisible by three, and the bracketed bit is where you plug in your "n = k" assumption. :D

Eliz.
 
Re: Mathematical Induction

Hello, flakine!

Prove that 22n1 is divisible by 3,  integers n1\displaystyle \text{Prove that }2^{2n} - 1\text{ is divisible by 3, }\forall \text{ integers n} \geqslant \text{1}

\(\displaystyle \text{Verify }S(1)\!:\quad 2^2-1 \;=\;3\quad\hdots \text{True}\)

Assume S(k) ⁣:22k1=3m  for some integer m.\displaystyle \text{Assume }S(k)\!:\quad 2^{2k} - 1 \:=\:3m\;\text{for some integer }m.


Add 3 ⁣ ⁣22k to both sides:22k+3 ⁣ ⁣22k1  =  3m+3 ⁣ ⁣22k\displaystyle \text{Add }3\!\cdot\!2^{2k}\text{ to both sides:}\quad 2^{2k} + 3\!\cdot\!2^{2k} - 1 \;=\;3m + 3\!\cdot\!2^{2k}

Factor:   [1+3]22k  =  3(m+22k)2222k  =  3(m+22k)22k+2  =  3(m+22k)\displaystyle \text{Factor: }\;\bigg[1 + 3\bigg]2^{2k} \;=\;3(m + 2^{2k}) \quad\Rightarrow\quad 2^2\cdot2^{2k} \;=\;3(m + 2^{2k}) \quad\Rightarrow\quad 2^{2k+2} \;=\;3(m + 2^{2k})

. . and we have:   22(k+1)  =  3(m+22k)multiple of 3\displaystyle \text{and we have: }\;2^{2(k+1)} \;=\;\underbrace{3(m + 2^{2k})}_{\text{multiple of 3}}


\(\displaystyle \text{We have established }S(k+1)\quad \hdots\quad\text{The inductive proof is complete.}\)

 
Re: Mathematical Induction

Although my predecessors have done a fine job of proving this, I would like to suggest another approach to proving 'such-and-such is divisible by P'.

Prove that the difference between consecutive expressions is divisible by P. (Theorem: if P | X and p | X-Y, then P | Y)

In this case: A(n) = 2^2n - 1

Assume A(n) is div by 3. I.e. 3 | 2^2n - 1
Prove A(n+1) if div by 3. I.e 3 | 2^2(n+1) - 1

Show that A(n+1) - A(n) is divisible by 3.

2^2(n+1) - 1 - (2^2n - 1) =

2^2n+2 - 2^2n =

2^2n(2^2 - 1) =

2^2n(3)

That's it.
 
Re: Mathematical Induction

Pklarreich said:
Although my predecessors have done a fine job of proving this, I would like to suggest another approach to proving 'such-and-such is divisible by P'.

Prove that the difference between consecutive expressions is divisible by P. (Theorem: if P | X and p | X-Y, then P | Y)

In this case: A(n) = 2^2n - 1

Assume A(n) is div by 3. I.e. 3 | 2^2n - 1
Prove A(n+1) if div by 3. I.e 3 | 2^2(n+1) - 1

Show that A(n+1) - A(n) is divisible by 3.

2^2(n+1) - 1 - (2^2n - 1) =

2^2n+2 - 2^2n =

2^2n(2^2 - 1) =

2^2n(3)

That's it.

That is an elegant proof...
 
Top