Expert: Paul Klarreich - 5/5/2009

Question
Hi Paul,
I believe the following proof question should be proved by contradiction.  Here is the question:

If a and n are natural numbers and a ≥ 2 and n ≥ 1,
then a²+1 ≠ 2ⁿ.

(In case the characters didn't work, this is what the proof says: If a and n are natural numbers and a is greater than or equal to 2 and n is greater than or equal to 1, then a squared plus 1 does not equal 2 to the nth power.)

If I use proof by contradiction, then I would assume the equation IS equal.  I'm lost after that.  I realize that I would need to prove that a is less than 2 and 1 is less than 1, but I'm not sure how.  Does the definition of an odd or even integer help in this case?

Thanks for your help!


Answer
Questioner:   Michelle
Country:  United States
Category:  Advanced Math
Private:  No
 
Subject:  Proofs- Proof by contradiction
Question:  Hi Paul,
I believe the following proof question should be proved by contradiction.  Here is the question:

If a and n are natural numbers and a ≥ 2 and n ≥ 1,
then a²+1 ≠ 2ⁿ.

(In case the characters didn't work, this is what the proof says: If a and n are natural numbers and a is greater than or equal to 2 and n is greater than or equal to 1, then a squared plus 1 does not equal 2 to the nth power.)

If I use proof by contradiction, then I would assume the equation IS equal.  I'm lost after that.  I realize that I would need to prove that a is less than 2 and 1 is less than 1, but I'm not sure how.  Does the definition of an odd or even integer help in this case?

Thanks for your help!
.......................................
Hi, Michelle,

The characters don't work for me.  I got your stuff fine, but I have to write:

<=  'less than or equal'
>=  'greater than or equal'
/=  'not equal'
2^n means '2 to the n'

That said, let's see about your proof:

For all  a >= 2  and n >= 1,

prove  a^2 + 1  /= 2^n

This is saying that 'one more than a square' is never a power of 2, except for trivial cases:

a = 1, n = 1:  1^2 + 1 = 2 = 2^1
a = 0, n = 0:  0^2 + 1 = 1 = 2^0
.......................................
Yes, I think definition of odd and even integers will work.


Case I. a is even:  a = 2k,  k >= 1


Now  a^2 + 1 = 4k^2 + 1, which is odd.

But 2^n is even, provided n >= 1.

So this is impossible.
....................
Case II.  a is odd:
a = 2k + 1  with  k >= 1

Then a^2 + 1 = 4k^2 + 4k + 2 = 2(2k^2 + 2k + 1)

Set  2(2k^2 + 2k + 1) = 2^n, with n >= 1

Divide out the 2:

2k^2 + 2k + 1 = 2^(n-1), with n-1 >= 0

Now the left side is odd, so the right side must be odd.
But the only power of 2 that is odd is 2^0 = 1.

Then 2k^2 + 2k + 1 = 1, so  k = 0.  But if k = 0, a = 1, which is not allowed.

This also is impossible, so both cases are disposed of.