1

(The problem) Use the principle of mathematical induction to prove that $2^n$ ≥ $n^2$ for n ≥ 4

Here's my solution on paper (https://i.stack.imgur.com/iJq7M.jpg)

(1) The Basis case is true: for n = 4 we have $2^4$ = $4^2$

(2) The Induction Step: Assume $2^k$ = $k^2$ is true for any k ≥ 4

(3) Solving for the Inductive hypothesis: I deduced that $2^k$ ≥ $k^2$ ⇒ $2(2^k$ ) ≥ $2(k^2)$ and I know that $2k^2$ ≥ $(k+1)^2$. By simplifying the binomial, I got $2k^2$ ≥ $k^2+2k+1$, now, if I subtract the left side to the right side we have $k^2-2k-1$ ≥ 0 and I also get $1-2/k^2-1/k^2$ ≥ 0 by dividing $(1/k)^2$ . Which if you look at the bottom of my paper, inputting some values of k lead me to think that this claim isn't true.

amWhy
  • 209,954
Youssef Mohamed
  • 318
  • 3
    Welcome to stackexchange. The statement is correct, so your proof is wrong somewhere. If you [edit] the question to show us your work (not an image) and tell us which parts you are unsure of we might be able to help. Use mathjax: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – Ethan Bolker Dec 20 '21 at 20:14
  • If you rewrite your question using MathJax, I would look at it. The image is unreadable on my computer. Otherwise, I will vote to close... – paul garrett Dec 20 '21 at 20:35
  • I think you have proved that $K^2 - 2K - 1\ge 0$ for $K\ge 4$, then by following your handwritten notes backward you can prove that $2^{K+1} \ge (K+1)^2$ for $K\ge 4$. Then why did you say "the statement is not true"? – peterwhy Dec 20 '21 at 20:39
  • I did rewrite it with MathJax , here is the format without it Use the principle of mathematical induction to prove that : 2^n >= n^2 for n >= 4 – Youssef Mohamed Dec 20 '21 at 20:39
  • @YoussefMohamed OK then, for $K\ge 4$, $K^2 - 2K - 1 > 0$, which implies that $K^2 - 2K - 1\ge 0$. – peterwhy Dec 20 '21 at 20:49
  • Your solution is not itself in MathJax. I cannot read it. – paul garrett Dec 20 '21 at 20:52
  • My solution is in the imgur link its a jpg https://i.stack.imgur.com/iJq7M.jpg – Youssef Mohamed Dec 20 '21 at 21:03

1 Answers1

6

Firstly, you made an error in your proof. You turned $2^{k+1}\geq(k+1)^2$ into $2k^2\geq(k+1)^2$ in the middle of the proof, which is a wrong implication. The statement you are trying to prove is true.

Secondly, even if you had made no error: failing to prove a statement is not equivalent to proving that the statement is wrong. You did not prove in any way that the statement is wrong. To do that, you would have to show that there exists a counterexample where $2^n<n^2$ for some $n\geq 4$.

Lastly, please use mathjax in the future so that your post is easily readable. Do not just photograph handwritten notes. MathJax basic tutorial and quick reference

Andreas Tsevas
  • 2,520
  • the point was if I proved that 2$k^2$ ≥$(k+1)^2$ then I proved that 2^k+1 ≥ $(k+1)^2$ as I assumed that 2^k+1 ≥ 2$k^2$ – Youssef Mohamed Dec 20 '21 at 20:32
  • 1
    @YoussefMohamed The implication not work in the opposite direction. Proving that $2k^2\geq(k+1)^2$ is false does not prove that $2^{k+1}\geq(k+1)^2$ is false. – Andreas Tsevas Dec 20 '21 at 20:47
  • @YoussefMohamed Also, $2k^2\geq (k+1)^2$ is true for all $k\geq 4$. Take another look at the end of your proof, it gets quite messy. – Andreas Tsevas Dec 20 '21 at 20:49
  • ur right about the that the implication doesn't work in the opposite direction i'll relook at it , but the statement 2$k^2$ ≥ $(k+1)^2$ is not true as $k^2$-2k-1 equals 0 at
    k= 1-sqrt(2) or 1+sqrt(2) which are less than 4     – Youssef Mohamed Dec 20 '21 at 21:01
  • 1
    @YoussefMohamed The statement $2k^2\geq (k+1)^2$ is true for all $k\geq 4$, which you need to prove. It does not matter what happens for $k<4$ at that point in the proof. – Andreas Tsevas Dec 20 '21 at 21:19
  • Bro, 2$k^2$ cannot equal $(k+1)^2$ for any value that is greater than or equal 4 that is what I mean , let me ask u the question in another way , what is the value of k that is equal than or greater than 4 that makes 2*$k^2$-$(k+1)^2$ =0 – Youssef Mohamed Dec 20 '21 at 21:37
  • @YoussefMohamed There is no such value of $k$. – Andreas Tsevas Dec 20 '21 at 21:41
  • @YoussefMohamed Let me ask you the question in another way, what is the value(s) of $k$ that is equal to or greater than $4$ that makes $2k^2-(k+1)^2\ge 0$? All of those $k$s. – peterwhy Dec 20 '21 at 21:52
  • Ok thank u I see I forgot that it great than or equal not greater than and equal , I need to go to sleep – Youssef Mohamed Dec 20 '21 at 22:24