Editing Mathematical induction (section)

== Examples ==
=== Sum of consecutive natural numbers ===
Mathematical induction can be used to prove the following statement {{math|''P''(''n'')}} for all natural numbers {{mvar|n}}.
<math display="block">P(n)\!:\ \ 0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.</math>

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: <math>0 = \tfrac{(0)(0+1)}2</math>, <math>0+1 = \tfrac{(1)(1+1)}2</math>, <math>0+1+2 = \tfrac{(2)(2+1)}2</math>, etc.

'''<u>Proposition.</u>''' For every <math>n\in\mathbb{N}</math>, <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}.</math>

'''Proof.''' Let {{math|''P''(''n'')}} be the statement <math>0 + 1 + 2 + \cdots + n = \tfrac{n(n + 1)}{2}.</math> We give a proof by induction on {{mvar|n}}.

''Base case:'' Show that the statement holds for the smallest natural number {{math|1=''n'' = 0}}.

{{math|''P''(0)}} is clearly true: <math>0 = \tfrac{0(0 + 1)}{2}\,.</math>

''Induction step:'' Show that for every {{math|''k'' ≥ 0}}, if {{math|''P''(''k'')}} holds, then {{math|''P''(''k'' +&thinsp;1)}} also holds.

Assume the induction hypothesis that for a particular {{mvar|k}}, the single case {{math|1=''n'' = ''k''}} holds, meaning {{math|''P''(''k'')}} is true:<math display="block">0 + 1 + \cdots + k = \frac{k(k+1)}2.</math>
It follows that:
<math display="block">(0 + 1 + 2 + \cdots + k )+ (k+1) = \frac{k(k+1)}2 + (k+1).</math>

[[Algebra]]ically, the right hand side simplifies as:
<math display="block">\begin{align}
\frac{k(k+1)}{2} + (k+1) &= \frac{k(k+1) + 2(k+1)}{2} \\
&= \frac{(k+1)(k+2)}{2} \\
&= \frac{(k+1)((k+1) + 1)}{2}.
\end{align}</math>

Equating the extreme left hand and right hand sides, we deduce that:<math display="block">0 + 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)((k+1)+1)}2.</math> That is, the statement {{math|''P''(''k'' +&thinsp;1)}} also holds true, establishing the induction step.

''Conclusion:'' Since both the base case and the induction step have been proved as true, by mathematical induction the statement {{math|''P''(''n'')}} holds for every natural number {{mvar|n}}. [[Q.E.D.]]

=== A trigonometric inequality ===
Induction is often used to prove [[inequality (mathematics)|inequalities]]. As an example, we prove that <math>\left|\sin nx\right| \leq n\left|\sin x\right|</math> for any [[real number]] <math>x</math> and natural number <math>n</math>.

At first glance, it may appear that a more general version, <math>\left|\sin nx\right| \leq n\left|\sin x\right|</math> for any ''real'' numbers <math>n,x</math>, could be proven without induction; but the case <math display="inline">n = \frac{1}{2},\, x=\pi</math> shows it may be false for non-integer values of <math>n</math>. This suggests we examine the statement specifically for ''natural'' values of <math>n</math>, and induction is the readiest tool.

'''<u>Proposition.</u>''' For any <math>x \in \mathbb{R}</math> and <math>n \in \mathbb{N}</math>, <math>\left|\sin nx\right| \leq n\left|\sin x\right|</math>.

'''Proof.''' Fix an arbitrary real number <math>x</math>, and let <math>P(n)</math> be the statement <math>\left|\sin nx\right| \leq n\left|\sin x\right|</math>. We induce on <math>n</math>.

''Base case:'' The calculation <math>\left|\sin 0x\right| = 0 \leq 0 = 0 \left|\sin x\right|</math> verifies <math>P(0)</math>.

''Induction step:'' We show the [[Logical consequence|implication]] <math>P(k) \implies P(k+1)</math> for any natural number <math>k</math>. Assume the induction hypothesis: for a given value <math>n = k \geq 0</math>, the single case <math>P(k)</math> is true. Using the [[List of trigonometric identities|angle addition formula]] and the [[Absolute value#Real numbers|triangle inequality]], we deduce:
<math display="block">\begin{align} 
\left|\sin(k+1)x\right|
&= \left|\sin kx \cos x+\sin x \cos kx\right| && \text{(angle addition)}
\\ 
&\leq \left|\sin kx \cos x\right| + \left|\sin x\,\cos kx\right| && \text{(triangle inequality)}
\\ 
&= \left|\sin kx\right|\left| \cos x\right| + \left|\sin x\right|\left|\cos kx\right| 
\\ 
&\leq \left|\sin kx\right| + \left|\sin x\right| && (\left|\cos t\right| \leq 1)
\\ 
&\leq
k\left|\sin x\right|+\left|\sin x\right| && \text{(induction hypothesis})\\ 
&= (k+1)\left|\sin x\right|.
\end{align}</math>

The inequality between the extreme left-hand and right-hand quantities shows that <math>P(k+1)</math> is true, which completes the induction step.

''Conclusion:'' The proposition <math>P(n)</math> holds for all natural numbers <math>n. </math>{{pad|4}} Q.E.D.