Induction Proof

**Rafael Almeida** · December 17th 2008, 06:50 PM

Hi all,

This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

"Prove that $3^n - 1$ is a multiple of 4 for all even numbers n"

Any help is appreciated. Thanks,

**Jhevon** · December 17th 2008, 06:55 PM

Originally Posted by Rafael Almeida

Hi all,

This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

"Prove that $3^n - 1$ is a multiple of 4 for all even numbers n"

Any help is appreciated. Thanks,

outline:

clearly the claim is true for n = 0.

assume it is true for any positive even integer n, that is, $3^n - 1 = 4k$ for some integer $k$ .

then, we have $3^{n + 2} - 1 = 3^2 \cdot 3^n - 1 = 3^2 \cdot 3^n - 3^2 + 8 = ...$

**ThePerfectHacker** · December 17th 2008, 08:05 PM

Originally Posted by Rafael Almeida

Hi all,

This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

"Prove that $3^n - 1$ is a multiple of 4 for all even numbers n"

Any help is appreciated. Thanks,

$3^{2n} - 1 = 9^n - 1 = (9-1)(9^{n-1}+9^{n-2}+ ... + 9 + 1)$
We see this number is even (pun!) divisible by 8.

**vinnybad** · December 18th 2008, 08:51 AM

Originally Posted by Rafael Almeida

Hi all,

This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

"Prove that $3^n - 1$ is a multiple of 4 for all even numbers n"

Any help is appreciated. Thanks,

Hey,

You get my first post ever

. I thought about it and I have a different approach which might be easier to understand.

T(n) = 3^n - 1

The task is proving that its a multiple of 4 for all even numbered n values.
2n is always even, and 4k is always a multiple of 4. (k is any other number...it's just for show in my opinion).

so it becomes:

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

make the left look somewhat like the right:

T(any even) = T(2n) = 3^(2n) - 1 = 3*3*3^n - 1.

We have odd * odd * (odd)^n - 1.

can we find a property about odd number multiplication? we might be able to...

Every odd number can be represented by 2p+1, where p is any number. In short, multiply any number by 2 (making it even) and add 1 (making it odd).

(2p+1)(2p+1) = (2p)^2 + 4p + 1

(2p)^2 = 4 * p^2 = 2 * 2 * p^2 ===> even
4 * p = 2 * 2 * p =====> even
1 ====> odd

prove even + even is always even
2p + 2j = 2 * (p+j) ===> 2 * some number ==> even

going backward to where the smiley is, we have:

odd * odd * odd^n - 1 = odd - 1 = even.

The explanation is long but depending on the person looking at it they would understand it right away or not...so we can see that we met the condition. The nice thing here is that the person didn't say the following:

3^n - 1 is an integer multiple of 4 where n is even and n > 1...so we can accept fraction * 4....

for ex, take n=3:
27-1=26 (not an integer multiple of 4 but it works)

**Last_Singularity** · December 29th 2008, 07:33 PM

Originally Posted by Rafael Almeida

Hi all,

This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

"Prove that $3^n - 1$ is a multiple of 4 for all even numbers n"

Any help is appreciated. Thanks,

Perhaps this will be more clear.

To simplify this problem, we can substitute $n=2k$ . Thus picking any $k \in N$ ensures that n is even. The problem then becomes

$3^{2k} - 1 = (3^2)^k - 1 = 9^k - 1$ is a multiple of 4 for all integers k.

Step 1: Check case base: $9^k - 1$ such that $k=0$ is $9-1=8$ , which is indeed a multiple of 4.

Step 2: Assume that $9^k - 1$ modulo 4 is 0. This is the claim for case where we have k.

Step 3 (induction step): Check that if $9^k - 1$ modulo 4 is 0, then $9^{k+1} - 1$ is also 0 modulo 4. This will show that if k works, then so will k+1. We do this as follows:

$9^{k+1} - 1 = 9(9^k) -1 = 9(9^k-1) + 8$

Thus, if $9^k - 1$ is 0 modulo 4, then multiplying it by 9 and adding 8 is also 0 modulo 4.

The proof is then complete.

Thread: Induction Proof

LinkBack

Thread Tools

Display

Induction Proof

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