Proof by induction that $2^n - 1 > n^2$

Question

i want to prove that $\forall n\geq 5$ $$2^{n}-1 > n^{2}$$

so the basis is trivial, and in the induction step (n+1), i stuck. i get :

$(n+1)^{2} = n^{2} + 2n + 1 < (2^{n} -1)+ 2n+1 = 2^{n} + 2n $

what i need to do from here? tnx!

Answer 1

Hint: $2^{n+1}-1 = 2\cdot (2^n - 1)+1$

Answer 2

You need to reach $2^{n+1}-1$ at the end, which equals $2^n + 2^n - 1$, and you already have $2^n + 2n$. If only you knew that $2^n-1 > 2n$, your task would be over. But you already know (induction hypothesis) that $2^n-1 > n^2$. Is this enough?

Answer 3

$$p(n): 2^n-1>n^2\\p(n+1):2^n-1>(n+1)^2\\ $$multiply p(n) by 2 $$2(2^n-1>n^2)\\2^{n+1}-2>2n^2\\2^{n+1}-1>2n^2+1\\$$ no try to prove $$2n^2+1>(n+1)^2 \\2n^2+1>n^2+2n+1\\n^2-2n >0\\n(n-2)>0\\$$it is correct because n>5

Answer 4

$2^n+2n<2^{n+1}-1$

To see this :

$2^{n+1}-1-2^n-2n=2^{n+1}-2^n-1-2n=2^n-1-2n>0$ for $n\geq 5$

Answer 5

for $k\geq2 ,2k^2+1>(k+1)^2$

$$2^{k+1}-1=2(2^k)-1=2(2^k-1)+1>2k^2+1>(k+1)^2$$

Answer 6

We have: $(n+1)^2 < 2^n+2n< 2^n + n^2 < 2^n + 2^n - 1 = 2\cdot 2^n - 1 = 2^{n+1} - 1$

Answer 7

You know that $2^n$ grows a lot quicker than $n^2$, so you can be quite generous. Since $n ≥ 5$,

$(n+1)^2 = n^2 + 2n + 1 < n^2 + 3n < n^2 + 5n ≤ 2n^2 ≤ 2 (2^n - 1) = 2^{n+1}-2 < 2^{n+1}-1$.