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

1. ## 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!

2. Hello pberardi
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$