Editing Mathematical induction (section)

=== 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.]]