0

In Susanna S. Epp's book Discrete mathematics with applications, she writes,"However, in many cases the proof of the implication for k>b does not work for a≤k≤b. So it is a good idea to get into the habit of thinking separately about the cases where a≤k≤b by explicitly including a basis step." This passage is after the passage where she introduces the principle of strong mathematical induction. I don't understand why the proof of the implication doesn't work for such cases. Isn't the implication vacuously true when k>b? Even more, I haven't yet seen a problem where the arbitrarily chosen integer k is less than or equal to some other arbitrarily chosen integer b. Isn't the whole point of mathematical induction proofs to pick a base integer b such that it is always smaller than some other integer k so that you can assume the two of them and any integer less than or equal to them to possess some property?

Zero dono
  • 1
  • 2
    Think of proving $2800\cdot n! > 10^n$. The obvious way to perform the inductive step $k\to k+1$ works only when $k\ge b:=10$. Nevertheless, the claim holds for all naturals, including $0\le k \le b$. (With a different factor, there might also be a few small exceptions) – Hagen von Eitzen Apr 06 '21 at 06:30
  • Susanna writes the inductive step of the proof as this, "[F]or every integer k≥b, if P(i) is true for every integer i from a through k, then P(K+1) is true." – Zero dono Apr 06 '21 at 06:52
  • But you have picked a k which is bigger than b – Zero dono Apr 06 '21 at 06:57
  • how can you prove it for a k smaller than that b – Zero dono Apr 06 '21 at 06:57
  • @Zerodono For $k<10$, there are $9$ explicit inequalities to check on a calculator to verify the inequality for those cases. There might be a more elegant proof, but even if you can't find one, checking those cases is a proof. The bigger point is there may not be a single argument that works for all $k$, but you are not required to find that to have a valid proof. – Ned Apr 06 '21 at 12:52
  • Thank you, Ned, for you answer pertaining to the example provided by Hagen. Can you address my question? – Zero dono Apr 06 '21 at 13:44
  • Hagen, why does the proof work only when k≥10? – Zero dono Apr 06 '21 at 14:23

0 Answers0