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)
Perhaps this will be more clear.
To simplify this problem, we can substitute . Thus picking any ensures that n is even. The problem then becomes
is a multiple of 4 for all integers k.
Step 1: Check case base: such that is , which is indeed a multiple of 4.
Step 2: Assume that modulo 4 is 0. This is the claim for case where we have k.
Step 3 (induction step): Check that if modulo 4 is 0, then is also 0 modulo 4. This will show that if k works, then so will k+1. We do this as follows:
Thus, if is 0 modulo 4, then multiplying it by 9 and adding 8 is also 0 modulo 4.
The proof is then complete.