# Need help with the algebra in an induction proof

• Feb 23rd 2010, 11:41 PM
morbius27
Need help with the algebra in an induction proof
Hi, I've been working on this problem for quite a while now and I just can't seem to get the algebra working for it. Any help is appreciated.

Determine the exact set of natural numbers n for which the inequality 2^n>=(n+1)^2 holds (1).

I have already found that this is true for n>=6 from intuition and plugging stuff in, but I need to prove this by induction.

Base case: n=6 holds for both sides

Induction step: I need to prove that (1) holds for n=k+1.
I tried plugging k+1 in for the left side, yielding 2^(k+1) = 2^k*2^1>=2*(k+1)^2 (from (1)) But this gets me nowhere as my ultimate goal is to arrive at 2^(k+1)>=((k+1)+1)^2
Any ideas?
• Feb 24th 2010, 10:34 AM
Hello morbius27
Quote:

Originally Posted by morbius27
Hi, I've been working on this problem for quite a while now and I just can't seem to get the algebra working for it. Any help is appreciated.

Determine the exact set of natural numbers n for which the inequality 2^n>=(n+1)^2 holds (1).

I have already found that this is true for n>=6 from intuition and plugging stuff in, but I need to prove this by induction.

Base case: n=6 holds for both sides

Induction step: I need to prove that (1) holds for n=k+1.
I tried plugging k+1 in for the left side, yielding 2^(k+1) = 2^k*2^1>=2*(k+1)^2 (from (1)) But this gets me nowhere as my ultimate goal is to arrive at 2^(k+1)>=((k+1)+1)^2
Any ideas?

Suppose that $\displaystyle P(n)$ is the propositional function: $\displaystyle 2^n >(n+1)^2$

Then $\displaystyle P(n)$
$\displaystyle \Rightarrow 2^n\times 2 > 2(n+1)^2$
$\displaystyle \Rightarrow 2^{n+1} > 2n^2+4n + 2$
$\displaystyle =n^2 + 4n + 4 +(n^2-2)$

$\displaystyle >(n+2)^2$, since $\displaystyle n^2-2 >0$ when $\displaystyle n\ge 6$
$\displaystyle \Rightarrow 2^{n+1} > ([n+1]+1)^2$
So $\displaystyle P(n) \Rightarrow P(n+1)$