0

Prove by induction that $$n^2 - n \ge 2$$ whenever $n$ is an integer $n \ge 2$. I am a total beginner at this, and don't know from where to begin. How do you prove this by induction correctly? Step-wise?

I seen some YouTube videos, however, this seems very confusing and different.

Albin M
  • 134
  • We need a clearer idea of why you're stuck. Can you do the base case? Can you state which "this inequality implies that inequality" theorem needs to be proven in the inductive step? Can you prove that theorem? – J.G. Apr 28 '22 at 15:16
  • 1
    assume for $n=k$, $k^2-k\geq 2$ and show for $n=k+1$, $(k+1)^2-(k+1)\geq 2$ – Lion Heart Apr 28 '22 at 15:19
  • 3
    Not an answer to the question. I wish instructors did not ask for inductive proofs of things much easier to prove directly. Since $n^2-n = n(n-1)$ and $n \ge 2$ this product is at least $2$. – Ethan Bolker Apr 28 '22 at 15:32

3 Answers3

4

Base Case: if $n=2$, then $n^2-n=4-2=2 \geqslant 2$. Inductive Case: Assume $n^2-n\geqslant 2$ for a fixed positive integer $n \geqslant 2$, we have:

\begin{equation*} (n+1)^2-(n+1)=n^2-n+2n \geqslant 2 + 2n >2 \end{equation*}

Therefore, $n^2-n\geqslant 2$ implies $(n+1)^2-(n+1)\geqslant 2$. We are done.

温泽海
  • 2,164
  • Hi, can you explain this? I want to understand how and why you derived to this? Thanks again. – Albin M Apr 28 '22 at 15:19
  • You want to prove the result for every positive integer $k\geqslant 2$. So you let a positive integer $k\geqslant 2$ be given and fixed. My prove shows that the result holds when $n=2$, hence $n=3$,...,hence $n=k$. – 温泽海 Apr 28 '22 at 15:23
  • Hi, can you explain this step-wise? I am not sure I follow entirely? Thanks. – Albin M Apr 28 '22 at 15:23
  • 1
    @AlbinM They have explained stepwise. You need to be more precise when saying what you’re confused about – FShrike Apr 28 '22 at 16:11
  • @温泽海, What if this was $n^2 - n \ge 0$ for $n \ge 1$ instead? How would your calculation be then? – Albin M May 01 '22 at 12:59
4

Base Case: $2^2-2\ge 2.\quad \checkmark$

Inductive step: Let $k\ge 3$. Assume that the statement holds for $n=k-1$, so $(k-1)^2-(k-1)\ge 2$. Then $$ k^2-k=(k-\tfrac12)^2-\tfrac14\ge (3-\tfrac12)^2-\tfrac14=6\ge 2. \quad \checkmark $$ This proves the statement for $n=k$, completing the inductive step.

Mike Earnest
  • 75,930
  • WHY: $(k - 1)^2 - (k - 1)$ ? – Albin M Apr 28 '22 at 18:29
  • WHY? $(k - 1)^2 - (k - 1)$ ? – Albin M May 02 '22 at 07:14
  • @AlbinM The reason should be apparent if you know the basics of how proofs by induction work. If you can reword your question to be more specific about what you find confusing, then I could maybe answer you. – Mike Earnest May 02 '22 at 16:09
  • The problem is, I know very little about the subject. – Albin M May 02 '22 at 16:54
  • 1
    Where are you trying to learn from? A class? A website? You should consult your learning materials, and compare against my answer. If you have no learning materials, then Math Stack Exchange (MSE) is not the place to go to learn. MSE is a supplement, not a primary learning source. – Mike Earnest May 02 '22 at 16:56
  • Thanks. I am sorry. – Albin M May 02 '22 at 17:06
2

There are 2 steps to an induction proof. (1) Verifying the base case and (2) The inductive step. Step (2) will require us to write down the induction hypothesis.

Theorem: If $n\geq 2$ is an integer, then $n^2-n\geq 2$.

(1) The base case here is $n=2$. The theorem says that $$n^2-n=2^2-2=2\geq 2$$ Indeed this is true and thus the base case is done.

(2) The induction hypothesis allows us to assume that for a fixed $N$, the theorem is true. Ie, $N^2-N\geq 2$.

We need to show that the theorem still holds if $N=n+1$.

Hence, let's take a look at $$(n+1)^2-(n+1)=n^2+2n+1-n-1=n^2+n$$ Now, we we want to apply the induction hypothesis, which tells us that $n^2-n\geq 2$, so lets do an algebraic trick: $$n^2+n=n^2-n+2n$$ But! The first two terms are what we see in the induction hypothesis, so we conclude $$n^2-n+2n\geq 2+2n$$ Now, note that if $n$ is any positive integer, $2+2n\geq 2$, which and putting all this together we get: $$(n+1)^2-(n+1)=n^2+n=n^2-n+2n\geq 2+2n\geq 2$$ and hence the induction step is completed.

By the principle of induction, the theorem is proved. Ie, if we ask ourselves if it holds for $n=10$, we know that it holds for $n=2$, and thus also holds for $n=3=2+1$, and thus also holds for $n=4=3+1=2+1+1$, and so on.

zz20s
  • 6,712
  • Hi, thanks. If this was $n^2 - n \ge 0$ for $n \ge 1$ instead? – Albin M May 01 '22 at 12:58
  • 1
    The proof will proceed in almost precisely the same way. First show that the base case $n=1$ is true by substituting $n=1$ directly into $n^2-n$. Then consider $(n+1)^2-(n+1)$ and use similar techniques to the ones I used here. – zz20s May 01 '22 at 13:50
  • So, in the final it would be: $1 + n \ge 1$ instead of $2 + 2n \ge 2$, right? – Albin M May 01 '22 at 15:11
  • 1
    How did you obtain that? – zz20s May 01 '22 at 15:15
  • Just, thought, because here you derived to $2 + 2n \ge 2$, if we look in your answer. So, I assumed that if, $n \ge 1$, then it must be 1. But, I am newbie so I don't really know. – Albin M May 01 '22 at 17:17
  • Can you show me some of your actual work? – zz20s May 01 '22 at 22:20
  • I haven't done anything. I am just, asking you: If it was, $n^2 - n \ge 0$ for whenever n is $\ge 1$ ? – Albin M May 02 '22 at 07:13
  • The answer is probably not then, though you could work out the algebra to see. – zz20s May 05 '22 at 04:05