Well, in my algorithms class, we are given a problem, and I just want to know if I am doing this proof by induction problem correctly. I think I am, but if I make an improper assumption, or some other stupid mistake, can someone correct me? Here is what I have:
Base case: 4^1 - 1 = 3. 3 is divisible by 3.
Assume: 4^n - 1 is divisible by 3.
4^(n+1) - 1 = (4^n)(4^1) - 1 = 4*4^n - 1 = 4*(4^n - 1) + 3
Since 4^n - 1 is divisible by 3, 4*(4^n - 1) is divisible by 3. And since 3 is divisible by 3, then 4*(4^n - 1) + 3 is divisible by 3. QED
Did I word my conclusion correctly, or should I change the wording?
Base case: 4^1 - 1 = 3. 3 is divisible by 3.
Assume: 4^n - 1 is divisible by 3.
4^(n+1) - 1 = (4^n)(4^1) - 1 = 4*4^n - 1 = 4*(4^n - 1) + 3
Since 4^n - 1 is divisible by 3, 4*(4^n - 1) is divisible by 3. And since 3 is divisible by 3, then 4*(4^n - 1) + 3 is divisible by 3. QED
Did I word my conclusion correctly, or should I change the wording?
.
Facebook
Twitter