What is the significance of Mathematical induction. Also, can a discussion be induced based on the problem stated below?

Question

If we observe a bug to be alive on the first day, and assume it to be alive on the Kth day, would we be able to prove that the bug would also be alive on the K+1th day? This statement seems so provable by mathematical induction; however, at the same time I know that the statement is false because all things die.

Now, could you explain to me, why is mathematical induction not applicable to this statement? Is mathematical induction flawed? I certainly acknowledge the fact that we do need some more information on the bug's story of life in order to derive something useful and check whether mathematical induction is applicable or not. But at the same time, I stress upon the fact that how do I find such conditions in other more logical cases, where I can successfully say that Mathematical induction is not applicable there?

Answer 1

You’re misunderstanding. Suppose

• we observe a bug to be alive today (I’m looking at one outside my window right now). This is the “base case”
• Next, suppose by some miracle/feat of mathematical/logical brilliance you are able to prove that for each $k$, the bug being alive on day $k$ implies it is alive on day $k+1$ (of course you will). This is the ‘meat’ of the induction.

Then the principle of induction tells you that the bug will remain alive forever.

Of course, we know the bug isn’t immortal. The gap in the reasoning is the second bullet point. We are not able to prove that “for all $k$, alive on day $k$ $\implies$ alive on day $k+1$”. Since we cannot prove our second bullet point, we cannot apply induction, so we are unable to conclude that the bug is immortal.

In fact, we can reason further and say the following: since we know that the bug is not immortal, one of the two bullet points above is false. It is not the first one, given what I said (I am observing it right now). Thus, the second bullet point is false; if you logically write out what this means, it says “there is a day $k$ such that the bug is alive on day $k$ but it is not alive on day $k+1$”.

---

My immortal phone.

Compare with the following idealized scenario where I prove using induction that my iphone will never die on me. I give you the following information

• I always sleep 12am-12pm
• one day I buy a phone at 12pm and it comes out of the box 100% charged
• my phone battery takes 12 hours to discharge completely and another 12 hours to charge completely
• every night I charge my phone right before sleeping.

With this information, it seems pretty obvious that my phone will never die on me during the day when I’m awake (ignoring realistic physics about battery decay and the fact that earth won’t be around forever etc etc). I can in fact provide a proof by induction:

On day 1 when I buy the phone, the second bullet point tells me that it is starting off with 100% charge, so it will last me the full first day 12pm-12am. This completes my base case.

Suppose on day $k$, my phone survives the full duration 12pm-12am. Now, keep in mind that by my first bullet point I am guaranteed to sleep at 12am-12pm; but my fourth bullet point says I will charge it right before sleeping. Since I sleep for 12 hours, and since by the third bullet point this is enough time for the phone to be fully charged, it follows that when I wake up on day $k+1$ at 12pm, my phone is fully charged. Since the phone takes a full 12 hours to discharge (bullet point 3) this means it will survive till 12am.

Therefore, I have shown that for all $k$, my phone surviving the entire day $k$ implies (by the given information about my habits and my phone’s capacity) it will survive the entire day $k+1$. Therefore, by induction, my phone will never run out of battery during the day.

Ok, let us ignore the silly human element about it being ‘my phone’ (I am obviously not immortal). Take this as merely being an example of how a proper inductive proof should run: establish base case (my first paragraph), then establish the inductive step using all the information you have in the problem (my second paragraph), then conclude. If the human element really bothers you, then reframe the scenario by adding another assumption: “there exists an immortal being”, and instead of calling it my phone, let’s refer to this immortal being’s phone :)

Answer 2

You are confusing hypotheses with conclusions. In brief, the induction step is part of the hypothesis of mathematical induction, and you are treating it incorrectly as if it were part of the conclusion of mathematical induction.

For a property $P(n)$ defined on the natural numbers, the hypothesis and conclusion of mathematical induction say this:

Hypothesis (Basis Step:) $P(1)$ is true; (Induction Step:) $P(k)$ implies $P(k+1)$ for all $k \in \mathbb N$.

Conclusion $P(n)$ is true for all $n \in \mathbb N$.

If you wished to apply mathematical induction to this bug's life, your job would be to verify that the hypothesis of mathematical induction are true:

Verify the basis step: the bug is alive on day 1. Also, verify the induction step: for each $k \in \mathbb N$, verify that if the bug is alive on day $k$ then the bug is alive on day $k+1$" (an impossible thing to verify, considering that it is false).

After you have completed these verifications, then you will be able to conclude: "For all $n \in \mathbb N$, the bug is alive in day $n$".