What is the connection between mathematical induction and implication?
I always see that mathematical induction is about
$$P(k)\implies P(k+1).$$
From what I know, mathematical induction works by finding a way to transform $P(k)$ into $P(k+1)$ and if you can do it, then you prove it.
Now, speaking in terms of logic formality, we can treat $P(k)$ as statement $A$, and treat $P(k+1)$ as statement $B$. We know that an implication is true if statement $A$ is true and statement $B$ is true; $A$ is false and $B$ is true/false (implication is false if $A$ is true and $B$ is false).
How can we know the truth value of statement $B$ ($P(k+1)$)? Is it the act of deriving $P(k+1)$ from $P(k)$ that makes statement $B$ have a value of true?
Best Answer
Unless I am seriously misunderstanding you, I think your question really amounts to:
That's a perfectly good question to ask. In fact, it is one of the most common questions I have encountered when teaching undergraduate mathematics over the last ten years or so. (Moreover, many students should ask this question, in the sense that they actually don't understand the logic of mathematical induction but either don't perceive their own lack of understanding or are not willing to verbalize it.) It's up there with big conceptual questions like "How does the $\epsilon,\delta$ definition of a limit work, logically speaking?" or "What is uniform convergence, logically speaking?" or "What is linear independence..."
These are key questions, but they are hard to answer in a vacuum. By that I mean that we often build a large portion of an undergraduate course around answering each of the above questions: there are prerequisites, training, several rounds of conceptual explanation of various kinds, examples, exercises, exams, and so forth. Without knowing where you are with respect to all these processes of undergraduate coursework, one (or at least, this one) can't give an explanation tailored to you: one can just try to repeat one of the blanket explanations that one gives in lectures.
So, for instance, I can point you to Chapter 2 of these lecture notes of mine, where induction is explored in great detail.
I can also say that in my department we have decided to place mathematical induction towards the end of an entire course devoted to introducing students to the concepts and methods of mathematical proof. I support that approach, as I have come to realize that induction is more logically complicated than most other proof techniques learned at this level. For instance, I think that in order to properly understand the logic of induction one needs to understand the logic of quantifiers. Thus one version of the Principle of Mathematical Induction is:
Principle of Mathematical Induction for Subsets: Let $S$ be a subset of the positive integers $\mathbb{Z}^+$ satisfying both of the following properties:
(POI1) $1 \in S$.
(POI2) For all $n \in \mathbb{Z}^+$, $n \in S \implies n+1 \in S$.
Then $S = \mathbb{Z}^+$.
My guess is that the place that you should concentrate your efforts is not solely or even primarily in the implication, but rather in understanding the meaning of the universal quantification in (POI2). Notice that that quantification is entirely missing in your description of mathematical induction: that's a symptom of the problem, I suspect.
I am honestly sorry not to be able to give a more useful answer. I have spent 2-3 weeks in undergraduate courses teaching induction and at the end had a substantial minority of the students who were still not fully comfortable with the logic of it. I wish I knew how to do better!
Added: I just clicked on the OP's profile and saw that s/he is 17 years old. Knowing that, I would say -- again, with all possible goodwill and in full knowledge that it could be frustrating to hear it -- to just have a little faith and patience: in my experience, most high school students who grapple with mathematical induction find it just a bit too abstract for them in some (I am imagining!) Piagetian sense. Most of these teenagers find that by the time they are just a year or two older they are simply cognitively more receptive to abstraction in general and mathematical induction in particular. For instance, once in my late 20's I was reminiscing with an old friend from high school who taken most the same (rather advanced, for our tender years and by the standards of our school) math courses as I had, and at one point he vouchsafed to me that he remembered that every once in a while I would say something about "mathematical induction", and that he never knew what the heck I was talking about but kept that to himself. He went on to study electrical engineering at a top American university, and when he saw mathematical induction in his courses then he had no trouble understanding it and was bemused by the silent mental block he had had about it as a high school student.
It may also be the case that high school courses which introduce mathematical induction (at least in the United States) are not very serious about it, do not expect most of the student to really grasp it, and in fact are not giving as good or careful an explanation as one would get in a university course. I learned about mathematical induction while taking a "self-paced precalculus course" over the summer at the age of 15. In self-paced courses, one actually starts at the beginning of the textbook, spends about five hours a day for three weeks reading the textbook, and keeps going until one gets to the end (and demonstrates at least some level of mastery of what was read). This meant that I got exposed to things that it turns out were not actually covered in most high school courses, or certainly not covered very well. Induction was always an "easy sell" for me (somewhat unfortunately, I think, for my current pedagogy), but for instance I remember reading about rotating conic sections to get rid of cross terms like $xy$ and being hella confused about what was going on. Once I learned linear algebra a couple of years later, all that stuff got a lot easier. (But there are still things that I read in my textbooks in that one self-paced course that I have literally never encountered again in 12 more years of schooling and 10 years of post-PhD mathematical research: for instance there is, I vaguely recall, something called a lattus rectum. I am starting to think that it was not actually so important!)