Home » Blog » Find the error in an inductive “proof”

Find the error in an inductive “proof”

Consider the statement:

    \[ A(n): 1 + 2 + \cdots + n = \frac{1}{8} (2n+1)^2. \]

  1. Prove that if the statement is true for an integer k, then it is also true for k+1.
  2. What is wrong with the claim that this proves that A(n) is true for all n?
  3. Make a change to turn this into a true statement and prove it for all positive integers.

  1. Proof. Assume the statement is true for an integer k. Then, adding k+1 to both sides of the formula we assume is true for the case k,

        \begin{align*}    1+2+\cdots + k + (k+1) &= \frac{1}{8} (2k+1)^2 + (k+1) & (\text{Ind. Hyp.}) \\    &= \frac{k^2}{2} + \frac{k}{2} + \frak{1}{8} + k + 1 \\    &= \frac{4k^2 + 12k + 9}{8} \\    &= \frac{1}{8} (2(k+1)+1)^2  \end{align*}

    Thus, the statement is true for k+1 if it is true for k. \qquad \blacksquare

  2. Of course, the above is not a proof by induction, and does not show that the statement is true for all n since we have not shown that it is true for any base case. We have shown that if it is true for some n, then it is true for n+1. To show that it is true for all n, we must show that it is true for the case n=1 (or some other starting point). As one can calculate, it is not true for n=1, or any other n for that matter.
  3. In the case n=1 we have 1 on the left, and \frac{9}{8} on the right. So, we make the following:
    Claim:

        \[ A(n): 1 + 2 + \cdots + n < \frac{1}{8} (2n+1)^2. \]

    Proof. We have already shown it is true for n=1 since 1 < \frac{9}{8}. Now assume it is true for some integer k, then using the inductive hypothesis and adding k+1 to both sides we have

        \begin{align*}   1 +2 + \cdots + k + (k+1) &< \frac{1}{8} (2k+1)^2 + (k+1) \\   &< \frac{1}{8} (4k^2 + 12k + 9) \\   &< \frac{1}{8} (2(k+1)+1)^2. \end{align*}

    Thus, the inequality is true for all n. \qquad \blacksquare

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):