proof by induction

**hmmmm** · January 28th 2009, 07:38 AM

prove by induction that 4^n-1 is divisible by three for all posotive integers of n
any help would be appriciated thanks.

**running-gag** · January 28th 2009, 07:51 AM

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$ .

**skeeter** · January 28th 2009, 08:01 AM

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.

**Soroban** · January 28th 2009, 08:11 AM

Hello, hmmmm!

Here's another way . . .

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.

Thread: proof by induction

LinkBack

Thread Tools

Display

proof by induction

Similar Math Help Forum Discussions

Proof by Induction

Proof by Induction

Mathemtical Induction Proof (Stuck on induction)

Proof by Induction??

Proof with algebra, and proof by induction (problems)

Search Tags