Proof this....

[TorontonianMath]

Hi,

I have this homework but I'm getting stuck...

Prove that n^2 <= (2^n) +1 holds for all n belonging to natural numbers.

Now it doesn't say what to use I was trying prove it using induction but I'm getting stuck...

Base Case: A(1)--> 1 <= 3 --> A(1) is true

Induction Hypothesis: A(n) is true

Induction Step: A(n+1) must also be true.

(n+1)^2 = n^2+2*n+1
<= 2^n + 1 + 2n + 1 (by induction hypothesis)
= 2^n + 2*n +2

then now I don't know what to do... any help and guidance will be greatly appreciated.

thanks!!!!

[HallsofIvy]

"Induction Step: A(n+1) must also be true.

(n+1)^2 = n^2+2*n+1
<= 2^n + 1 + 2n + 1 (by induction hypothesis)
= 2^n + 2*n +2"

And you want "<= 2^(n+1)+ 1". The problem is that 2^n+ 2n+ 2 is NOT <= 2^(n+1)+ 1 for n= 1 (2+ 2+ 2= 6 is NOT <= 2^2+ 1= 5). I noticed that for n= 1, 1^2= 1< 2^1+ 1= 3, for n= 2, 2^2= 4< 2^2+1= 5, but for n= 3, 3^2= 9= 2^3+1. Then "<" is true for n>3. I would recommend doing n<= 3 "by hand", then assuming in your induction that n> 3. You might also want to prove, by a separate induction, that for n> 2, 2k< 2^k.