Prove using induction: $n^2 - 7n + 12 \geq 0$, where $n \geq 3$

Question

Does this work as an inductive prood? It feels like of weird, I might be doing the basis step twice unecessarily...

Answer 1

If for every integer $n \geq 3$ we let $P(n)$ be the statement $n^2 - 7n + 12 \geq 0$, then to prove that $P(n)$ is true for all such $n$, we need to show that $P(3)$ and $\forall n \geq 3(P(n) \implies P(n+1))$ are true. In any proof by mathematical induction, a person doesn't need to carry around the notation "$P(n)$". In fact, doing so makes the proof ugly, so let's not include it below.

Proof. If $n=3$, then $n^2-7n+12 = 9 - 21+12 = 0 \geq 0$.

Now let $n$ be an arbitrary integer satisfying $n \geq 3$, and suppose that $n^2 - 7n + 12 \geq 0$. Then $$\begin{align*} (n+1)^2 - 7(n+1)+12 &= (n^2+2n+1)-(7n+7)+12 &&\\ &= (n^2 - 7n + 12) + (2n + 1 - 7) &&\text{(after rearranging)}\\ &\geq 2n + 1 - 7 &&\text{(since $n^2 - 7n + 12 \geq 0$)}\\ &\geq 2(3)+1-7 &&\text{(since $n \geq 3$)}\\ &= 0.&& \end{align*}$$ Therefore, by mathematical induction, $n^2 - 7n + 12 \geq 0$ is true for every integer $n \geq 3$.

Answer 2

Hint

Let $f(n) = n^2 - 7n + 12$. For the inductive step, compute $f(n+1) - f(n)$.

Answer 3

The induction need not "feel weird". Here is a more conceptual way to view it.

Notice that $\rm\ f(n+1) = f(n) + 2(n-3) \ge f(n)\:$ for $\rm\:n\ge 3,\:$ i.e. $\rm\,f(n)\,$ is $ $ increasing $ $ for $\rm\:n\ge 3.\:$ Applying an obvious inductive proof shows that $\rm\:f(n)\:$ stays $\ge$ its initial value, i.e. $\rm\:f(n)\ge f(3)=0,\:$ for all $\rm\:n\ge 3,\:$ as was to be proved.

The same idea works more generally for any function $\rm\,f(n)\,$ on $\rm\,\Bbb N\,$ whose successive differences are nonnegative, $ $ i.e. $ $ if $\rm\ \Delta f(n) = f(n+1)-f(n) \ge 0\,\:$ for $\rm\,n\ge n_0,\ $ then $\rm\:f(n)\,$ is increasing there, thus it remains $\,\ge\,$ its initial value: $\rm\:f(n)\ge f(n_0)\:$ for all $\rm\:n\ge n_0.\:$

Therefore, it suffices to prove by induction this very simple property of increasing functions on $\,\Bbb N.\,$ After this slight abstraction, the induction step is much clearer: it amounts to nothing but lifting up the inequality using the transitivity of $\,\ge,\ $ namely $ $ (with $\rm\,n_0 = 0\:$ for clarity)

$$\rm f(n+1)\ge f(n),\ f(n)\ge f(0)\ \Rightarrow\ f(n+1)\ge f(0)$$

Essentially the induction telescopically collapses the chain of hypothesized inequalities:

$$\rm f(n+1) \ge f(n) \ge \cdots \ge f(0) \ \Rightarrow\ f(n+1)\ge f(0)$$

The term "telescopy" is used to describe this since it is analogous to collapsing the multiple tubes of a telescope into a single tube. There are similar forms of telescopy that are ubiquitous in inductive proofs, especially additive and multiplicative forms that occur when computing sums and products.

You can find further discussion of this and related topics in many prior posts here. Mastering these ideas will go a long way towards making inductive proofs appear more mathematical than magical. Inductively pulling rabbits out of hats is a job for magicians, not mathematicians!

Answer 4

Is not necessary induction. $$ n^2-7n+12=n^2-3n-4n+12=n(n-3)-4(n-3)=(n-3)(n-4)$$ $$n=3 \Leftrightarrow 0 \geq 0$$ $$n=4 \Leftrightarrow 0\geq0$$ For $n=5$ the relation is $>0$.

Here is induction step. $$(n+1)^2-7n-7+12=n^2-5n+6=n^2-3n-2n+6=n(n-3)-2(n-3)=(n-2)(n-3)$$ which is also true for $n \geq 3$.