Prove some formulas using mathematical induction

by RoRi

July 2, 2015

Use mathematical induction to prove the following:

$\displaystyle{1+2+3+ \cdots + n = \frac{n(n+1)}{2}}.$
$\displaystyle{1+3+5+ \cdots + (2n-1) = n^2}.$
$\displaystyle{1^3 + 2^3 + 3^3 + \cdots + n^3 = (1+2+3 + \cdots + n)^2}.$
$\displaystyle{1^3+2^3+ \cdots +(n-1)^3 < \frac{n^4}{4} < 1^3 + 2^3 + \cdots + n^3}.$

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$
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$
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$
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$

Related

7 comments

September 29, 2018 at 4:52 pm

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.

Reply
- September 30, 2018 at 6:10 pm
  
  Oliver Golde says:
  
  lmao nevermind
  
  Reply
  - August 26, 2020 at 1:40 pm
    
    Scattergories says:
    
    Could u please explain? I find myself pondering on the same questions u mentioned
  - January 12, 2023 at 1:15 am
    
    Navadeep says:
    
    Adding the terms (6k^2 + 4k + 1)/4 in first case doesn’t affect our inequality.
    If 1^3+2^3+…+k^3 < (k^4+4k^3)/4 .
    Then 1^3+2^3+…+k^3 will definitely be lesser than a much bigger RHS, i.e., (k^4+4k^3)/4+(6k^2 + 4k + 1)/4.
    Inequality holds good even after introducing new terms to RHS of inequality.
    Adding the new terms doesn't affect our inequality and after simplification proves 1^3+2^3+…+k^3 < (k+1)^4 / 4.
    Similarly for second case even after subtracting (6k^2 +8k + 3)/4 from LHS of our inequality , the inequality still holds since if
    (k^4+4k^3+12k^2 + 12k + 4)/4 < 1^3+2^3+…+(k+1)^3
    then making LHS even much smaller by subtracting (6k^2 +8k + 3)/4 .
    the new result (k^4+4k^3+6k^2 + 4k + 1)/4 will definitely be lesser than 1^3+2^3+…+(k+1)^3 .
    Subtracting the new terms doesn't affect our inequality and after simplification proves (k+1)^4 / 4 < 1^3+2^3+…+(k+1)^3
- September 30, 2018 at 6:11 pm
  
  Oliver Golde says:
  
  lmao nvm
  
  Reply
May 6, 2016 at 4:40 pm

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

Reply
- May 6, 2016 at 4:47 pm
  
  RoRi says:
  
  Yeah, typo, it should be $4k$ so in the numerator we have $(k+1)^4$ . Fixed now.
  
  Reply

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