proof by induction

• January 28th 2009, 07:38 AM
hmmmm
proof by induction
prove by induction that 4^n-1 is divisible by three for all posotive integers of n
any help would be appriciated thanks.
• January 28th 2009, 07:51 AM
running-gag
Hi

Initialization of induction is easy.

Let's suppose that for a given n $4^{n}-1$ is divisible by 3.
You need to demonstrate that $4^{n+1}-1$ is divisible by 3.
Hint : $4^{n+1}-1 = 4(4^{n}-1)+3$.
• January 28th 2009, 08:01 AM
skeeter
prove $4^n - 1$ is divisible by 3

true for $n = 1$

assume true for $n$, show true for $(n+1)$ ...

since $4^n - 1$ is divisible by 3, then $4^n - 1 = 3k$ , $k$ a positive integer.

$4^n - 1 = 3k$

$4(4^n - 1) = 4(3k)$

$4^{n+1} - 4 = 12k$

$4^{n+1} - 1 - 3 = 12k$

$4^{n+1} - 1 = 12k + 3$

$4^{n+1} - 1 = 3(4k + 1)$

since $(4k+1)$ is also a positive integer, $4^{n+1} - 1$ is a multiple of 3, and therefore, is divisible by 3.
• January 28th 2009, 08:11 AM
Soroban
Hello, hmmmm!

Here's another way . . .

Quote:

Prove by induction that $3|(4^n-1)$ for all positive integers $n.$

Verify $S(1)\!:\;\;4^1-1 \:=\:3$ . . . true

Assume $S(k)\!:\;\;4^k-1 \:=\:3a\,\text{ for some integer }a.$

Add $3\!\cdot\!4^k$ to both sides: . ${\color{blue}3\!\cdot\!4^k} + 4^k - 1 \;=\;3a + {\color{blue}3\!\cdot\!4^k}$

Factor: . $(3 + 1)4^k - 1 \;=\;3\left(a + 4^k\right)$

. . . . . . . . $4\!\cdot4^k - 1 \;=\;3\left(a + 4^k\right)$

. . . . . . . . $4^{k+1}-1 \;=\;\underbrace{3\left(a + r^k\right)}_{\text{a multiple of 3}}$

We have proved $S(k+1)$ . . . The inductive proof is complete.