Preface : (Skip this part if you want to go straight to my question. I am writing this so hopefully it doesn't get a duplicate since I couldn't find any satisfactory answer at mathstackexchange yet). Hello, I would like ask why I am failing to understand the Mathematical Induction is always valid. I am aware that this is a very common question being asked and I know there are many attempts to explain why, but I have been having this question for a long time (Actually coming back here to ask since I did not succeed for months). Trust me I have read many posts and answers related to this topic all over the different websites and none of them still satisfied my understanding (including mathstackexchange). I will try to explain clearly where I am confused so hopefully someone can help me.
So from what I know, Mathematical Induction proves that a statement $P(n)$ is true for all natural number if:
- $P(0)$ is true.
(My understanding: Mathematical statement is true when $n = 0$.)
- Assuming $P(n)$ is true for all natural numbers and if I can show that the implication $P(n) \rightarrow P(n+1)$ is true.
(My understanding: Meaning we don't know if the statement P(n) it's true or false. But if we show that the implication $P(n) \rightarrow P(n+1)$ holds then that is enough for mathematical induction to hold whether the statement $P(n)$ is actually true or not).
If these conditions (1) and (2), holds then that proves that the statement $P(n)$ is true for all natural numbers.
Here is where I find mathematical Induction being fishy.
I am fine with this logic of mathematical induction whenever the statement $P(n)$ is actually true, and the conditions (1) and (2) satisfies. Then I can agree with the common answers I've seen: If $P(0)$ is true and since $P(n) \rightarrow P(n+1)$ is true, $P(1)$ is true. Since $P(1)$ is true with the same logic $P(2)$ is true and so on…
But from what I know, the logical implication has a truth table of a form:
So it is saying that the implication is only false when the statement is true but the result is false. Meaning it is also possible for implication being true when the starting statement $P$ is false. If I am understanding implication correctly (Please correct me if I am wrong), when the statement $P \rightarrow Q$ is true, it means after applying valid logical steps to the initial statement $P$ (whether the statement $P$ is true or not), you can get to the resulting statement $Q$.
I was okay with false statement implying false result being true and false statement implying true statement being true with the following examples:
ex1) False statement implies False statement can be true:
Let the statement $P$ be $-1 = 1$ and result $Q$ be $0 = 2$. I am assuming $P$ and $Q$ are both false for obvious reason. Now since implication is applying logical steps, I can add $1$ to both sides of the statement $P$. This results in $-1 + (1) = 1 + 1 \rightarrow 0 = 2$ which is the statement $Q$. Therefore the implication is true.
ex2) False statement implies true statement can be true:
Let the statement $P$ be $-1 = 1$ and result $Q$ be $1 = 1$. I am assuming $P$ is false for obvious reason but $Q$ is true. Now since implication is applying logical steps, I can square both sides of the statement $P$. This results in $(-1)^2 = (1)^2 \rightarrow 1 = 1$ which is the statement $Q$. Therefore the implication is true.
Now back to the mathematical induction, we have $P(0)$ being true, we assume the statement $P(n)$ is true for all natural number not just $0$ (meaning it could also be false for some numbers greater than $0$, but we don't know) and we show that the implication $P(n) \rightarrow P(n+1)$ is true. But from the logic that I just said, $P(n)$ could be false and still imply $P(n) \rightarrow P(n+1)$ is true. If $P(n)$ is a true statement, applying logical steps should get me to $P(n+1)$ because that is how mathematics is built (To get logical answer from logical steps). But if we don't know if the statement $P(n)$ is false and the implication turns out to be true then what? It still seems like the logic of If $P(0)$ is true and since $P(n) \rightarrow P(n+1)$ is true, $P(1)$ is true. Since $P(1)$ is true with the same logic $P(2)$ is true and so on… should work. But as I said if it turns out that $P(n)$ is not true for all natural number, this shouldn't be the case and I can't imagine what the result would be.
I am assuming there should exist some statement $P(n)$ being false for some natural number (True for $P(0)$) but still true for $P(n) \rightarrow P(n+1)$ since logic says it is possible for a false statement to imply true statement and there are infinitely many statements that can satisfy this (I am assuming…).
I tried to come up with my own example of this and I couldn't but in case this will help people who reads this can understand better on where I am getting wrong I will still put it:
Let the statement $P(n)$ on natural number be $$\sum_{n=0}^k (n+1)^{3n} = k!3^k$$.
We can show the base case $P(0)$ is true.
Assuming that this statement is true for all natural number and applying logical steps, I get a contradiction and fail to show that implication is false. (Maybe it is possible to show that the implication is true by doing clever tricks?). In this case the example turns out to fail, but I believe there should be such a statement $P(n)$ that would satisfy my reasoning.
So where am I getting wrong? Why am I thinking that such a $P(n)$ should exist and why shouldn't it exist?
I hope I was clear and if there is any ambiguity or questions please ask.
Best Answer
Suppose you want to prove the hypothesis that $\forall b\in N: P(b)$ and that you have already shown that $P(0)$ is true.
Let $k$ be any element of $N$.
We can prove that $P(k)\implies P(k+1)$ in the usual way by first assuming that $P(k)$ is true and then proving that $P(k+1)$ must also be true.
Technically, we could also do either of the following (not necessarily the same thing for each value of $k$):
What about simply proving $P(k)$ is false as you suggested (corresponding to lines 3 and 4 of the truth table)? As we see from (2) above, doing so would falsify the initial hypothesis.