0

I’ve noticed it’s conventional in most literature to state the base case as a lower bound in an inductive hypothesis. So for example if the base case is P(1) then in the inductive hypothesis P(k) it’s usually stated that k is a positive integer greater than or equal to 1.

But is it even necessary to state this? The goal of induction is to show that $P(k) \implies P(k+1)$ and use the base case to prove it for every integer onwards. To show this one must only show that $P(k+1)$ holds if $P(k)$ is assumed to be true so bounds don’t seem to matter if there isn’t a case where the first part is true but the second isn’t. (Of course you still have to prove the base case)

Is there any reason induction is usually written with bounds then?

More specifically, I'm asking if the highlighted part is actually necessary: More specifically, I'm asking if the highlighted part is actually necessary:

So far, I've seen cases of texts on induction including bounds and others not including restrictions at all.

Angela
  • 89
  • 3
    I can show that if $n$ is an integer, then $n+1$ is an integer. So, does that mean that $4.5$ is an integer, since I can apply the rule to $3.5$? – Rushabh Mehta Nov 12 '19 at 18:49
  • Well 3.5 isn’t an integer so you can’t say anything about 4.5. If you could however show that 3.5 was an integer then sure. – Angela Nov 12 '19 at 18:51
  • 2
    The analogy that I learned when first tackling induction is that it is like a line of dominoes standing on end. Showing a base case is true is akin to pushing over one of the dominoes and the induction step is how as one domino falls it pushes down the next one in the line as well. We would have all dominoes from that point on be knocked over. Without having pushed down that first domino however they can all stay standing up. – JMoravitz Nov 12 '19 at 18:53
  • I’m not saying you don’t need to show the base case is true, just saying that you don’t usually need any bounds at all in the inductive hypothesis (for example take a look at Wikipedia’s definition of induction which has bounds) – Angela Nov 12 '19 at 18:54
  • 1
    As for cases where the first is true but the second isn't... consider proving that for all integers $n\geq 6$ that $(n-5)(n-3)$ is positive. Well... plugging in $n=2$ to that we have a positive result, but for $n=3$ it is zero and $n=4$ it is negative... – JMoravitz Nov 12 '19 at 18:56
  • I think your question is very specific: "is it essential, in mathematical induction, that the statements be indexed by the natural numbers?" The answer to that is, no. You can easily come up with statements that are true for any integer greater than $-100$, say. Sticking to the natural numbers is just a convenience. Of course, I might not have understood your question properly. – lulu Nov 12 '19 at 18:58
  • Yes in there you need to state bounds but in many cases you don’t because many induction problems don’t ever have cases like that where either your proof or the thing you’re trying to prove falls apart with an earlier base case. – Angela Nov 12 '19 at 18:58
  • 3
    Then I don't understand your complaint... there are very definitely cases where $k\geq k_0$ is a necessary assumption in proving $P(k)\wedge k\geq k_0\implies P(k+1)$ efficiently and correctly. Are you just saying that you would prefer in some cases to simplify this as $P(k)\implies P(k+1)$ leaving $k\geq k_0$ out from the list of assumptions? So long as the implication still holds, go ahead... more power to you. That doesn't excuse you from doing it for all induction examples since, as mentioned previously, in some it is critical information that must be kept. – JMoravitz Nov 12 '19 at 19:07
  • What we need is that $P(n_0)$ is true for some natural number $n_0$ and that assuming true $P(k) \implies P(k+1)$ also true for any $k\le k_0$ with $k_0\le n_0$. – user Nov 12 '19 at 19:15
  • Clearly induction only proves the result for $k \ge k_0$ where $k_0$ is your base case. It may not always be necessary to know that $k \ge k_0$ to prove that $P(k) \implies P(k+1)$, but it is never useful to prove $P(k) \implies P(k + 1)$ for $k < k_0$, since even if you do, you still do not know if $P(k)$ is true for any $k < k_0$. Thus there is never any loss in including $k \ge k_0$ in your conditions, whether or not there is any gain. – Paul Sinclair Nov 13 '19 at 04:13

0 Answers0