Mathematical induction - what makes it true? I am trying to work through an example in my book and it just seems nonsensical

Why is mathematical induction a valid proof technique? The reason comes from the well ordering property, listed in Appendix 1, as an axiom for the set of positive integers, which
  states that "every nonempty subset of the set of positive integers has a least element". So, suppose
  we know that $P(1)$ is true and that the proposition $P(k)\to P(k + 1)$ is true for all positive
  integers $k$. To show that $P(n)$ must be true for all positive integers $n$, assume that there is at
  least one positive integer for which $P(n)$ is false. Then the set $S$ of positive integers for which
  $P(n)$ is false is nonempty. Thus, by the well-ordering property, $S$ has a least element, which
  will be denoted by m.We know that $m$ cannot be $1$, because $P(1)$ is true. Because $m$ is positive
  and greater than $1$, $m − 1$ is a positive integer. Furthermore, because $m − 1$ is less than $m$, it is
  not in $S$, so $P(m− 1)$ must be true. Because the conditional statement $P(m− 1)\to P(m)$ is
  also true, it must be the case that $P(m)$ is true. This contradicts the choice of $m$. Hence, $P(n)$
  must be true for every positive integer $n$." 

I am getting confused at a lot of parts of this. So assuming that $P(1)$ is true and assuming that $P(k)$ implies $P(k+1)$ for all positive integers, why do I have to show that one positive integer is false to show that it must be true? I don't understand that.
Anyways now my set S of $P(n)$ false inputs is now not empty. So that element is now $m$, and $m$ must be positive so then they claim $P(m-1)$ must be true because it is less than $m$. Why is this true? For example why can't I have $5$ and $4$ both being false where $m$ is $5$? Why does $P(m -1)$ imply $P(m)$? There doesn't seem to be proven anywhere. They then claim that $P(m)$ must now be true even though they previously claimed that it was false, so how can that be? It seems like the contradiction works to disprove the original assessment that $P(n)$ must be true.
 A: You don't have to show that one positive integer is false in order to show that the proposition is false.  
Notice that the quoted proof says: 

assume that there is at least one positive integer for which $P(n)$ is false.

That's something of a clue already.  In mathematics, you can't prove something by first assuming that it's true.  Instead, this is an example of a proof by contradiction.  We start out by assuming that what we are trying to prove is false, and then derive a contradiction.  Since we assume that the axioms of mathematics are sound, this means that our original assumption must be false, and hence that what we are trying to prove is true.  
In this case, we want to prove that $P(n)$ is true for all $n$.  The negation of that statement is that $P(n)$ is false for some $n$.  We now work with this assumption and try to derive a contradiction.  
We now let $m$ be the smallest number such that $P(m)$ is false.  It's very important that $m$ is the smallest such example, which is why we need the well-ordering principle.  In order to make the dependence on the well-ordering principle explicit, we say: 

Let $S$ be the set of $n$ such that $P(n)$ is false.  By assumption, $S$ is non-empty, so it must have a least element $m$ by the well-ordering principle.  

But you don't have to think that way.  Intuitively, if there is one counterexample among the natural numbers, there must be a smallest one.  (Note that the same is not true if we restrict attention to the integers, which do not satisfy the well-ordering principle.  For example, $\{-1, -2, -3, \dots\}$ hasn't got a least element.  
Now consider $P(m-1)$.  Since $m$ is the smallest number with $P(m)$ false, and $m-1$ is smaller than $m$, $P(m-1)$ must be true.  
The reason you can't have both $P(4)$ and $P(5)$ false when $m$ is $5$ is that $m$ has to be the smallest counterexample, and it clearly isn't in this case, as $4$ is a smaller counterexample.  In this case $m=4$ (or some smaller number).  
$P(m-1)$ implies $P(m)$ by assumption.  We are trying to show that $P(n)$ is true for all $n$ when we are given these pieces of information: 


*

*$P(1)$ is true.

*If $P(k)$ is true then $P(k+1)$ is true.  


We obviously need some information about $P$ to prove that $P(n)$ is true for all $n$, and this is the information we are given.  Now, setting $k=m-1$, and noting that $P(m-1)$ is true, we must have that $P(k+1)=P((m-1)+1)=P(m)$ is true.  
We have now arrived at a contradiction.  This serves to disprove our initial assertion that $P(n)$ is not true for some $n$.  It does not disprove the theorem that we are trying to prove - that $P(n)$ is true for all $n$.  Indeed, since it disproves the negation of that theorem, it proves the theorem and we win.  
A: Mathematicians are super fond of proof by contradiction. Maybe this will make more sense:
Assume we have an inductive argument, and assume we've arbitrarily decided it doesn't work for some numbers. Let's say the smallest number it doesn't work for is 17. Then it works for 16. But since we know that if it holds for $n$ it holds for $n+1$, it holds for $16+1=17$. Contradiction, there's no smallest number the induction argument doesn't hold for, and so induction holds for every positive integer. Hooray for contradictions!
A: "why do I have to show that one positive integer is false to show that it must be true?"
In a proof by contradiction, you assume something is false in order to prove it is true.  You do that by showing that the assumption that it is false leads to a contradiction.
Here's an example: Suppose we want to prove $\log_2 3$ is an irrational number, i.e. it is not equal to $m/n$, where $m$ and $n$ are some integers.
So we assume $\log_2 3$ is rational, i.e. it is $m/n$ for some integers $m$ and $n$.  Since $\log_2 3$ is positive, $m$ and $n$ are both positive or both negative.  If they're both negative, we can multiply them both by $-1$ and have them both positive.  Then we have
$$
\begin{align}
\log_2 3 & = \frac m n \\[12pt]
2^{m/n} & = 3 \\[12pt]
2^m & = 3^n \\[12pt]
\text{The even number }2^m & \text{is equal to the odd number }3^n.
\end{align}
$$
But a number cannot be both even and odd, so the assumption has led to a contradiction.  Since the assumption that $\log_2 3$ is rational leads to a contradiction, it must be that $\log_2 3$ is not rational.
"they claim $P(m-1)$ must be true because it is less than $m$. Why is this true?"
Because $m$ is the SMALLEST number for which $P(m)$ is not true.  Hence any smaller number is one for which $P$ is true.
"Why does $P(m-1)$ imply $P(m)$?"
That depends on WHICH proof by induction you're doing.  The point is that their whole argument applies in contexts in which one can prove that if $P(m-1)$ then $P(m)$.  Situations in which you cannot prove that certainly exist, but those are situations in which you cannot write a proof by induction, and their argument is not intended to apply to such cases.
A: The $P(x)$ notation can become daunting sometimes. Let me show you a problem that is in fact parallel to the one you are trying to solve but it is not full of $``P"$. Suppose you are given that $\mathbb N = \{1,2,3, \cdots\}$ is the set of natural numbers. I claim that, if the set $\mathbb S$ has the following properties, then $S = \mathbb N$.
$$S \subseteq \mathbb N \tag{1}$$
$$1 \in S \tag{2}$$
$$n \in S \implies n+1 \in S \tag{3}$$
To tie this problem to yours, let $S = \{n \in \mathbb N | P(n) = TRUE\}$.
Let $M = \mathbb N\backslash S$ be the set of all natural numbers that are not in $S$. Then, if we can show that $M = \varnothing$, it will follow that $S = \mathbb N$. We start by assuming that $M \ne \varnothing$. We will show that this assumption leads to a contradiction. Hence $M = \varnothing$.
Because of condition $(1)$, $M \subseteq \mathbb N$. By hypothesis, $M$ is not an empty set. Hence, by WOP, there exists a natural number $s$ that is the smallest member of $M$.
By condition $(2)$, $s \ne 1$. People tend to gloss over this part, but it is a very important detail. Because $s \in \mathbb N$ and because $s \ne 1$, then $s-1 \in \mathbb N$. Since $s$ is the smallest member of $M$, then $s - 1 \not \in M$. But, since $s-1 \in \mathbb N$, by condition $(3)$, $s \in S$.
 But, because $s \in M$, then $s \not \in S$.
So because our assumption that $M$ was a non empty set lead to a contradiction, we conclude that $M = \varnothing$. It follows that $S = \mathbb N$.
