Principle of Mathematical Induction/Warning

From ProofWiki
Jump to navigation Jump to search

Principle of Mathematical Induction: Warning

It is a common mistake when setting up a proof by induction to forget to check the base case.

This can cause incorrect reasoning.


Example 1

Let $L_k$ denote the $k$th Lucas number.

Let $F_k$ denote the $k$th Fibonacci number.


Given that $L_n = F_n$ for $n = 1, 2, \ldots, k$, we see that:

\(\ds L_{k + 1}\) \(=\) \(\ds L_k + L_{k - 1}\) Definition 1 of Lucas Number
\(\ds \) \(=\) \(\ds F_k + F_{k - 1}\) by assumption
\(\ds \) \(=\) \(\ds F_{k + 1}\) Definition of Fibonacci Number


Hence:

$\forall n \in \Z_{>0}: F_n = L_n$


Example 2

We are to prove that:

$\dfrac 1 {1 \times 2} + \dfrac 1 {2 \times 3} + \dotsb + \dfrac 1 {\paren {n - 1} \times n} = \dfrac 3 2 - \dfrac 1 n$


For $n = 1$ we have:

$\dfrac 3 2 - \dfrac 1 n = \dfrac 1 2 = \dfrac 1 {1 \times 2}$

Assuming true for $k$, we have:

\(\ds \dfrac 1 {1 \times 2} + \dfrac 1 {2 \times 3} + \dotsb + \dfrac 1 {\paren {n - 1} \times n} + \dfrac 1 {n \times \paren {n + 1} }\) \(=\) \(\ds \dfrac 3 2 - \frac 1 n + \dfrac 1 {n \paren {n + 1} }\) by the induction hypothesis
\(\ds \) \(=\) \(\ds \dfrac 3 2 - \frac 1 n + \paren {\dfrac 1 n - \dfrac 1 {n + 1} }\)
\(\ds \) \(=\) \(\ds \dfrac 3 2 - \frac 1 {n + 1}\)

But clearly this is wrong, because for $n = 6$:

$\dfrac 1 2 + \dfrac 1 6 + \dfrac 1 {12} + \dfrac 1 {30} = \dfrac 5 6$

on the left hand side, but:

$\dfrac 3 2 - \dfrac 1 6 = \dfrac 4 3$

on the right hand side.


Example 3

We are to prove that:

$1 + 3 + 5 + \dotsb + \paren {2 n - 1} = n^2 + 3$


We establish as an induction hypothesis:

$1 + 3 + 5 + \dotsb + \paren {2 k - 1} = k^2 + 3$


Then:

\(\ds 1 + 3 + 5 + \dotsb + \paren {2 k - 1} + \paren {2 k + 1}\) \(=\) \(\ds k^2 + 3 + \paren {2 k + 1}\) from the induction hypothesis
\(\ds \) \(=\) \(\ds k^2 + 2 k + 1 + 3\)
\(\ds \) \(=\) \(\ds \paren {k + 1}^2 + 3\) Square of Sum


But clearly this is wrong, because for $n = 2$, say:

\(\ds \paren {2 \times 1 - 1} + \paren {2 \times 2 - 1}\) \(=\) \(\ds 1 + 3\)
\(\ds \) \(=\) \(\ds 4\)

on the left hand side, but:

$2^2 + 3 = 7$

on the right hand side.


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Principle_of_Mathematical_Induction/Warning&oldid=511955"