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

[flakine]

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

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

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

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

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

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

\(\displaystyle \text{ = 2}^\text{2} 2^{2k} - 1\)

\(\displaystyle \text{ = }2^{2k} \bullet 4 - 1\)

\(\displaystyle \text{ = ??????? }\)

\(\displaystyle \text{How do I get there from here, please provide your reasoning}\text{. Thanks!}\)

 

[stapel]

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.

Eliz.

 

[soroban]

Re: Mathematical Induction

Hello, flakine!

\(\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}\)

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


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

\(\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})\)

. . \(\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.}\)

 

[Pklarreich]

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.

 

[Deleted member 4993]

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.

That is an elegant proof...