# induction - I got most of the proof, just cant finish

• May 7th 2009, 07:42 PM
pberardi
induction - I got most of the proof, just cant finish
Prove that for every natural number greater than or equal to 6, (n+1)^2 is less than or equal to 2^n

Let S = {n in N s.t. n>=6, (n+1)^2 <= 2^n }

Show 6 is in S 7^2 <= 2^7
Assume n is in S
Show n+1 is in S
(n+2)^2 <= 2^n +1
n^2 + 4n + 4 <= 2^n +1 HELP!
• May 8th 2009, 01:01 AM
Hello pberardi
Quote:

Originally Posted by pberardi
Prove that for every natural number greater than or equal to 6, (n+1)^2 is less than or equal to 2^n

Let S = {n in N s.t. n>=6, (n+1)^2 <= 2^n }

Show 6 is in S 7^2 <= 2^7
Assume n is in S
Show n+1 is in S
(n+2)^2 <= 2^n +1
n^2 + 4n + 4 <= 2^n +1 HELP!

$n \in S \Rightarrow (n+1)^2 \le 2^n$

$\Rightarrow n^2 + 2n+1 \le 2^n$

$\Rightarrow n^2 + 4n+4 \le 2^n + 2n+3$

$\Rightarrow (n+2)^2 \le 2^n + 2+2n+1$

$\Rightarrow (n+2)^2 \le 2^n + n^2 + 2n + 1$, since $2 < n^2$ for $n \ge 6$

$\Rightarrow (n+2)^2 \le 2^n + (n+1)^2$

$\Rightarrow (n+2)^2 \le 2^n +2^n$, since $(n+1)^2 \le 2^n$

$\Rightarrow (n+2)^2 \le 2.2^n = 2^{n+1}$

Incidentally, to show $6 \in S$, you should write $7^2 \le 2^6$, not $2^7$