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!

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$

Grandad

Thanks for the clear proof and explanation sir.