first principle of mathematical induction
First principle of mathematical induction
Mathematical induction is a proof technique designed to prove statements about all natural numbers. Its validity as a valid proof technique may be established as a consequence (full proof at bottom) of a fundamental axiom of positive integers, though it is to note that this is just one the ways to view induction.
The basic idea of mathematical induction is that every natural number can be "reached" from zero (or one depending on the definition). Let \[P(n):n<2^{n}\] and suppose we wished to prove that whenever \[P(n)\] is true for each positive integer \[n\]. Suppose we could prove that whenever \[P(k)\] is true for some positive integer \[k\], then \[P(k+1)\] is also true. We could use this to finish the problem as follows: since \[P(1)\] is true, \[P(2)\] must be true; since \[P(2)\] is true, \[P(3)\] must be true; and so on.
Keep in mind that we're not assuming that \[P(k)\] is true, instead we're trying to prove that if \[P\] is true for a particular \[k\] (not all \[k\]), then it's also true for \[k+1\]. Furthermore, induction itself isn't the process of proving \[P(k)\implies P(k+1)\], it's the statement that "if \[P(1)\] and \[P(k)\implies P(k+1)\] is true, then \[P\] is true for all natural numbers".
Definition
It is very commonly referred to as just mathematical induction, weak induction or principle of mathematical induction. It's usually taken as an axiom.
Let \[P(n)\] be an open sentence, where the domain of \[n\] is \[\mathbb{N}\]. If \[P(1)\] is true, and for each \[k\] in \[\mathbb{N}\], if \[P(k)\] is true then \[P(k+1)\] is true, \[P(n)\] is true for each \[n\] in \[\mathbb{N}\].
Alternatively, we can write it as if \[P(1)\] is true and \[\forall\,k\in \mathbb{N},\,P(k)\Rightarrow P(k+1)\], then \[P(n)\] is true for each \[n\in \mathbb{N}\].
An intuitive way to think of mathematical induction is to think it as a ladder with infinitely many rungs, with the bottommost rung labelled as 1. We begin climbing this infinite ladder by holding onto the first rung (\[P(1)\] is true), then, we reach for the second rung, assuming we can grab it (\[P(1)\] is true then \[P(2)\] is true), we can hoist ourselves up to the second rung and reach for the third rung, so on and so forth (for each \[k\] in \[\mathbb{N}\], if \[P(k)\] is true then \[P(k+1)\] is true). With this chain of logic, we will be able to reach any given rung, thus proving that \[P(n)\] must be true.
Proof by induction can start at any integer
Sometimes, we don't necessarily start at \[P(1)\], maybe a proposition is false for small numbers. However, this method of proving still works.
Let \[a\in \mathbb{Z}\], and let \[P(n)\] be a proposition whose domain includes the set \[S=\left\{ n\in \mathbb{Z}:n\ge a \right\}\]. If \[P(a)\] is true and \[P(k)\implies P(k+1)\] for each \[k\in S\], then \[P(n)\] is true for each \[n\in S\].
A simple trick we can use to prove the above statement is by defining \[P^{\prime}(n)=P(n+a-1)\], then we have a correspondence between \[P\] and \[P^{\prime}\]:
which makes it clear that if we can prove \[P^{\prime}(n)\] for all \[n\in \mathbb{N}\] then we will have proved \[P(n)\] for whatever set of numbers we're trying to prove. Furthermore, for each \[k\in \mathbb{N}\], \[P^{\prime}(k)\implies P^{\prime}(k+1)\] holds since \[P(k+a-1)\implies P((k+1)+a-1)\].
Therefore, by induction, \[P^{\prime}(n)\] is true for each \[n\in \mathbb{N}\], so \[P(n)\] is true for each \[n\in S\].
General outline
- Identify what we're trying to prove, i.e. the open sentence \[P(n)\]
- Verify that \[P(1)\] is true, usually done by direct substitution or giving a valid example
- Assume that \[k\] is some natural number and \[P(k)\] is true, then show that \[P(k+1)\] is true
Example
We want to prove that for any \[x\in \mathbb{R}\] and \[n\in \mathbb{N}\], we have \[(1+x)^{n}\ge1+nx\].
Let \[n=1\], \[(1+x)^{n}=1+x=1+nx\]. Base case is verified to be true.
Suppose that the result is known for some arbitrary natural number, \[k\] , i.e. \[(1+x)^{k}\ge 1+kx\]. Now consider the case \[k+1\]:
Therefore, we've shown that \[P(k)\implies P(k+1)\]. By induction, the proposition holds for all \[n\in \mathbb{N}\].
Equivalence between the well-ordering principle and the first principle of mathematical induction
It is usually said that the induction axiom is equivalent to the well-ordering principle. However, this only applies over standard \[\mathbb{N}\] (or classical logic), as they are technically not equivalent (Öhman, Lars–Daniel, 2019). The paper can be summarised (in a very oversimplified manner) as, the fifth Peano axiom, which is the induction axiom only fits for the standard \[\mathbb{N}\], while if replaced with the well-ordering principle as the fifth axiom will allow sets not limited to the standard \[\mathbb{N}\], which doesn't fit the original five Peano axioms. The author thus argues that due to this, the induction axiom and well-ordering principle can not equivalent relative to Peano's first four axioms.
Now with that out of the way, we'll prove by contradiction that WOP implies the first principle of mathematical induction.
Let \[S\] be a non-empty set where \[1\in S\] (zero or one both works, one is just purely by convention), and \[x\in S\] implies that \[x+1\in S\]. Let \[J\] be the set of all natural numbers that are not in \[S\]. Assume \[J\] is non-empty for contradiction.
By well-ordering principle, \[J\] has a least element. Call it \[k\], so obviously \[k\in J\]. \[k\ne1\] because we've established \[1\in S\], so \[k>1\], thus it follows that \[k-1\in \mathbb{N}\]. Since \[k\] is the least element in \[J\], \[k-1\notin J\implies k-1\in S\]. This implies that \[k\in S\] as \[\left( k-1 \right)\in S\implies \left( k-1 \right)+1\in S\]. \[k\in S\] contradicts with the fact that \[k\in J\], therefore \[J\] must be an empty set, which follows that \[S=\mathbb{N}\]. This result shows that \[\mathbb{N}\] is a set where \[x\in \mathbb{N}\] implies that \[x+1\in \mathbb{N}\], thus also showing that mathematical induction is a valid proof technique.