# 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!
$\displaystyle n \in S \Rightarrow (n+1)^2 \le 2^n$

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

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

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

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

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

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

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

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