Logic and Proof Exercises

Answer

Nope; n = 2 is a counterexample: 3(2) – 1 = 6 – 1 = 5, which isn't even. There are plenty of others, too.

Answer

Yes. The base case when n = 1 gives us 2¹ + 1 = 3, which is odd. We assume 2^k + 1 is odd, then prove 2^{(k + 1)} + 1 is odd, too. To do that, we rewrite the expression as 2(2^k) + 1, then split it up even further to get 2^k + 2^k + 1. We know that first 2^k is an even number 'cause it's a power of 2, and we know 2^k + 1 is odd from our induction hypothesis, so (2^k) + (2^k + 1) = (even number) + (odd number). The sum of an even and odd number is always odd (like 4 + 3 = 7, etc.), so our sum must be an odd number. Boom, proof done.

Answer

Bzzzt, that's false. We can't even get past our base case. When n = 1, we get 4¹ + 3¹ = 7. That's definitely not divisible by 2.