Home » Blog » Prove some formulas using mathematical induction

Prove some formulas using mathematical induction

Use mathematical induction to prove the following:

  1. \displaystyle{1+2+3+ \cdots + n = \frac{n(n+1)}{2}}.
  2. \displaystyle{1+3+5+ \cdots + (2n-1) = n^2}.
  3. \displaystyle{1^3 + 2^3 + 3^3 + \cdots + n^3 = (1+2+3 + \cdots + n)^2}.
  4. \displaystyle{1^3+2^3+ \cdots +(n-1)^3 < \frac{n^4}{4} < 1^3 + 2^3 + \cdots + n^3}.
  1. Proof. The statement is true for n = 1 since on the left we have 1 and on the right, 1(1+1)/2 = 1.
    Assume then that the statement is true for n=k \in \mathbb{Z}_{>0}. Then,

        \begin{align*}   &&1+2+\cdots+k &= \frac{k(k+1)}{2} & (\text{Ind. Hyp.}) \\ \implies && 1+2+ \cdots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) & (\text{Adding } k+1 \text{ to both sides}) \\ \implies && 1+2 + \cdots + (k+1) &= \frac{k^2+3k+2}{2}\\ &&&= \frac{(k+1)(k+2)}{2}. \end{align*}

    Hence, if the statement is true for k, then it is true for k+1. Thus, since we have shown it is true for n=1, we have the statement is true for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

  2. Proof. The statement is true for n=1 since on the left we have 1 and on the right, 1^2 =1.
    Assume then that the statement is true for n =k \in \mathbb{Z}_{>0}. Then,

        \begin{align*}  && 1+3+5 + \cdots + (2k-1) &= k^2 & (\text{Ind. Hyp.}) \\  \implies && 1+3+5 + \cdots + (2k-1) + (2(k+1)-1) &= k^2 + 2(k+1) -1 & (\text{Adding } 2(k+1)-1)\\  \implies && 1+3+5 + \cdots + (2k-1) + (2k+1) &= k^2 + 2k + 1 \\ &&& = (k+1)^2. \end{align*}

    Hence, if the statement is true for k, then it is true for k+1. Thus, since we have shown it is true for n=1, we have the statement is true for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

  3. Proof. The statement is true for n =1 since on the left we have 1^3 = 1 and on the right, 1^2 = 1.
    Assume then that the statement is true for n = k \in \mathbb{Z}_{>0}. Then,

        \begin{align*}  && 1^2 + 2^3 + \cdots + k^3 &= (1+2 + \cdots + k)^2 & (\text{Ind. Hyp.}) \\  \implies && 1^3 + 2^3 + \cdots + k^3 &= \left (\frac{k(k+1)}{2} \right)^2 & (\text{Part (a)})\\  \implies && 1^3 + 2^3 + \cdots + k^3 + (k+1)^3 &= \left( \frac{k(k+1)}{2}\right)^2 + (k+1)^3 & (\text{Adding } (k+1)^3)\\  &&& = \frac{1}{4} (k^4 + 2k^3 + k^2) + (k^3 + 3k^2 + 3k + 1) \\  &&& = \frac{1}{4} (k^4 + 2k^3 + k^2 + 4k^3 + 12k^2 + 12k + 4) \\  &&& = \frac{1}{4} ((k+1)^2(k+2)^2) \\  &&& = \left( \frac{(k+1)(k+2)}{2} \right)^2 \\  &&& = (1 + 2 + \cdots + (k+1))^2 & (\text{Part (a)}) \end{align*}

    Hence, if the statement is true for k, then it is true for k+1. Thus, since we have shown it is true for n=1, we have the statement is true for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

  4. Proof. The statement is true for n = 1 since the term on the left is 0^3 = 0, the term in the middle is 1^4 / 4 = 1/4, and the term on the right is 1^3 = 1. Since 0 < \frac{1}{4} < 1, the statement is indeed true for n =1.
    Assume then that the statement is true for some n =k \in \mathbb{Z}_{>0}. Then, the induction hypothesis gives us,

        \[ 1^3 + 2^3 + \cdots + (k-1)^3 < \frac{k^4}{4} < 1^3 + 2^3 + \cdots + k^3. \]

    Taking the left inequality first, we have

        \begin{align*}  && 1^3 + \cdots + (k-1)^3 &< \frac{k^4}{4} \\ \implies && 1^3 + \cdots + (k-1)^3 + k^3 &< \frac{k^4}{4} + k^3 & (\text{Adding } k^3)\\ \implies && 1^3 + \cdots + k^3 &< \frac{k^4 + 4k^3}{4} \\ \implies && 1^3 + \cdots + k^3 &< \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4} & (\text{Adding positive terms to the right})\\ \implies && 1^3 + \cdots + k^3 &< \frac{(k+1)^4}{4}. \end{align*}

    Thus, if the inequality on the left is true for k then it is true for k+1. Since we have shown it is true for n =1, we have that it is true for all n \in \mathbb{Z}_{>0}.
    Now, for the inequality on the right

        \begin{align*}  && \frac{k^4}{4} &< 1^3 + \cdots + k^3 \\ \implies && \frac{k^4}{4} + (k+1)^3 &< 1^3 + \cdots + (k+1)^3 & (\text{Adding } (k+1)^3) \\ \implies && \frac{k^4}{4} + k^3 + 3k^2 + 3k + 1 &< 1^3 + \cdots + (k+1)^3 \\ \implies && \frac{k^4 + 4k^3 + 12k^2 + 12k + 4}{4} &< 1^3 + \cdots + (k+1)^3 \\ \implies && \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4} &< 1^3 + \cdots + (k+1)^3 & (\text{Making the left smaller})\\ \implies && \frac{(k+1)^4}{4} &< 1^3 + \cdots + (k+1)^3. \end{align*}

    Thus, if the inequality on the right is true for k, it is also true for k+1. Hence, since we have established that it is true for n =1, we have that it is true for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

5 comments

  1. Oliver Golde says:

    Sorry for my lack of understanding, but I don’t see how the answer for (d) makes sense. Part of the way through for the first case, you ‘add positive terms to the right’ without changing the left hand side of the inequality. In the next case you ‘make the left smaller’ without changing the other side of the inequality again. I see that you add the 6k^2 + 4k + 1 in the numerator in the first case and subtract 6k^2 +8k + 3 from the numerator in the second case. What am I missing? Any feedback would be greatly appreciated. And sorry again for not getting it.

  2. Sebastian says:

    Dude shouldnt the second inequality from the bottom have a 4k instead of a 6k, the one that has the (making it smaller) sentence. Cause u cant really transform it if thats not the case.

    Idk maybe im wrong cause im just learning how to prove things with induction XD

    Btw awesome site, i love it :D

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