# Thread: Induction Proof

1. ## Induction Proof

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,

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

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

4. 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)

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