Mathematical Induction#
Mathematical induction is a proof technique used to establish the truth of an infinite sequence of statements. It consists of two main steps:
Base Case: Verify that the statement is true for the initial value, usually \(n = 0\) or \(n = 1\).
Inductive Step: Assume that the statement is true for some arbitrary value \(n = k\) (inductive hypothesis), and then prove that it is true for \(n = k + 1\).
By completing these steps, one can conclude that the statement holds for all natural numbers \(n\).
Example: Let’s use mathematical induction to show that
for all integers \(n \geq 1\).
Our induction hypothesis claims that the equation holds for every \(k\). That is,
Then, we want to prove that the equation also holds for \(k + 1\).
From the above equations, let’s take their left-hand side and compare them.
Base Case: let’s verify the base case \(n = 1\). Using the equation for this,
Inductive Step: next, we need to verify that such equality also holds true for \(n = k + 1\). By replacing the equations in the above comparison we have
Finally,
Which concludes our proof. We can see that our proof consisted of three main steps:
Verify that the base case (n = 1) holds true.
Assume by our induction hypothesis that the equation holds true for \(n = k\).
From the equality where \(n = k + 1\), our goal was to show that indeed the sequence \(1 + 2 + 3 + \cdots + (k + 1)\) is equal to \(\frac{(k + 1)(k + 2)}{2}\).