In proof by induction, what does it mean when condition for inductive step is lesser than the propsition itself?

121 Views Asked by At

enter image description here

My question is regarding the question posed at the end of the proof.

My answer is that the result does not hold for all $m \ge 7$ because when $m=7$, the result is $343 \le 128$, which is false.

Is there another way to answer this sort of question besides directly trying different values until you get a false result?

EDIT:

Another question I have regarding this solution is:

In the proof for the inductive step, we start by assuming $k \ge 10$. But along the way, the author mentions $k \ge 1$ and $k \ge 7$ to justify the inequality.

Why do we bother to do this instead of just sticking with $k \ge 10$?

3

There are 3 best solutions below

2
On BEST ANSWER

Even if the case $m=7$ worked, $\textit{this proof}$ would not prove the result for $m=7$ because the base case is at $10$ and we apply induction to prove only for all $m\ge 10$.

0
On

"We only need $k \geq 7$ for the inductive step" is referring strictly to assertion that $k^3 + 7k^2 \leq k^3 + k^3$ within the argument of the inductive step. (See the chain of inequalities.) When $k = 7, \;k^3 + 7k^2 = 7^3 + 7\cdot 7^2 = 7^3 + 7^3$, which is true

Essentially, since the proposition we are aiming to prove, which applies to $k \geq 10$, assures that since $10>7$, we know that the step $k^3 + 7k^2 \leq k^3 + k^3$, because that mini-claim holds for any $k\geq 7$, so that mini-claim certainly holds for $k\geq 10$.

RE: you edit

The author states those claims along the way in the inductive step as a way of stating the minimal requirement at the respective claims for the claim to be true. And since $k\geq 10 \implies k\geq 7$, so any claim that is true for $k \geq 7 is certainly true for $k \geq 10. Likewise, $k \geq 10 \implies k \geq 1$. That's all.

0
On

That $k \ge 7$ is only used to establish the inequality that $ 7k^2 \le k^3$, which is just one step in the proof. That $k \ge 7$ is stated only for clarification: the initial assumption is that $k \ge 10$ which also leads to $ 7k^2 \le k^3$, but is not quite so clear.