Before I get into my question, I'd like to apologize if this is a silly one. I am still new to induction so I am trying to wrap my head around it.
My textbook states that the principle of mathematical induction is deduced from the Well-Ordering Principle (WOP). This I understand.
However, I was thinking that if mathematical induction is based on the fact that we have a basis step – that we prove to be true and we then go on to say assume that $P(n)$ is true for some $n$, then we prove $P(n+1)$ is true for some $n$, and this is basically like an iteration over and over again that repeats so many times that eventually all values become true – why can't we just show that if $P(1)$ is true and $P(2)$ is true, then $P(n)$ is true based on the principal of mathematical induction? Where is the issue with this?
Also, why is it that when we prove for $P(n+1)$ that we sub in $P(n)$. I understand the logic behind it, but why does assuming that if the statement we assumed to be true, which was, $P(n)$, makes up a part of $P(n+1)$, then $P(n+1)$ is true. For e.g., we know that $P(n)$ is the statement $1 + 3 + \ldots + (2n-1) = n^2$ and we prove the basis step and for the inductive step, we assume that it is true for some $P(n)$. Then we say "show $P(n+1)$ is true" and we do so by saying $1 + 3 + \ldots + (2n – 1)+ (2n + 1) = (n+1)^2$ because from $1$ to $(2n-1)$ that is $n^2$ and $n^2 + 2n + 1 = (n+1)^2$. What if that $2n + 1$ was false? This would make the implication false. Do we just assume it is true? If so, why?
Thank you in advance.
Best Answer
Because $P(3)$ is not guaranteed to hold. For the statement to hold for all natural numbers, we need it to hold for a certain value $n$, and prove that from this, $P(n + 1)$ holds. This way, we can substitute any natural $n$ and say that it holds for all natural numbers.
An example would be to find the number of regions a given set of nonparallel lines where no three of them are concurrent. For $n = 1, 2$, we have $P(n) = 2, 4$. Now, if we try to get the value of $P(3)$ from the values of $P(1)$ and $P(2)$, it seems as if $P(3)$ is either $6$ or $8$. As it turns out, $P(3) = 7$. This shows that we can't just say that $P(n)$ holds just because $P(1)$ and $P(2)$ holds.
I don't quite understand what you mean here. If I try to, it seems as if you don't understand why, if $P(n)$ holds, then $P(n + 1)$ holds.
This is what we are trying to prove using induction. We prove that the base case(s) hold, and assume that for a particular value $n$, $P(n)$ holds. After we do this, we try to prove that $P(n + 1)$ holds based from what we got from $P(n)$.
You provided the example where the sum of the first $n$ odd numbers $P(n)$ is $n^2$. We prove this by first proving the base case ($n = 1$) which holds $(1 = 1)$. We then assume that for a certain value $n$, $P(n) = n^2$ holds. How do we prove that $P(n + 1) = (n + 1)^2$? We know that odd numbers are of the form $2k - 1$ for a natural number $k$. The $(n + 1)$th natural number is $2(n + 1) - 1 = 2n + 1$. We know that $P(n + 1)$ is the sum of the first $n + 1$ odd numbers, and so, $P(n + 1) = P(n) + (2n + 1)$. By assuming that $P(n) = n^2$, we can see that $P(n) = n^2 + 2n + 1$ which can be factored out to $P(n + 1) = (n + 1)^2$. Since this statement is the same as $P(n) = n^2$, it must be that, for all $n$, $P(n) = n^2$. This is also what you stated which is true.
What if, at some point, it really doesn't hold? Then that set of values are the counterexamples to the claim and the statement doesn't hold for all natural numbers.