5
$\begingroup$

I am trying to understand how to write mathematical induction proofs. This is my first attempt.

Prove that the sum of cubic positive integers is equal to the formula $$\frac{n^2 (n+1)^2}{4}.$$ I think this means that the sum of cubic positive integers is equal to an odd number. However, let's go on proving...

1) I start by proving the base case $n=1$ and I show that the formula holds.

2) I assume than any number $k$ other than $1$, which appartains at $N$, holds for the formula and I write the same formula but with $k$ which replaces $n$.

3) For mathematical induction, I assume that the formula holds also for $k+1$ = $n$ So, the left side of the equation should be:

$$\sum^{k+1}_{i=1} i^3 = 1^3 + 2^3 + 3^3 + ... + (k+1)^3$$

I am wondering about which one of these 2 forms (equivalents, I think) should have the right side :

this one, with $k+1$ in place of the $n$ of the original formula / or $k$ in the second version: $\frac{(k+1)^2[(k+1)+1]^2}{4}$ or this one: $\frac{k^2(k+1)^2 }{4} + (k+1)^3$ ?

I think that, in order for the proof to be convincing, we should write an equivalent statement for the original form of the formula, namely $$\sum^{n}_{i=1} i^3= \frac{n^2(n+1)^2}{4}$$ and perhaps we do it by showing that after algebraic passages $\frac{k^2(k+1)^2 }{4} + (k+1)^3$ is equal to $\frac{(k+1)^2[(k+1)+1]^2}{4}$ ?

Sorry for my soliloquy but it helps to understand and I would appreciate confirmation from you!

$\endgroup$
8
  • 4
    $\begingroup$ "appartains at $N$" what on earth does that mean / have to do with anything? $\endgroup$ Oct 27, 2015 at 12:04
  • 2
    $\begingroup$ I am confused by your aside about odd numbers. 1 + 8 + 27 is not an odd number. $\endgroup$ Oct 27, 2015 at 14:11
  • $\begingroup$ As an aside, I've often found it helpful in induction to think about the inductive step first, and then the base case. In the inductive step, you show that if it works for n, then it works for n+1. Then you have the motivation for the base case: how do I know whether it works for, say, 17? Well, it would work for 17 if it works for 16, and it would work for 16 if it works for 15, and ..., all the way back to 1. Now just show it for 1 (or whatever the appropriate base case is), and you're all set. $\endgroup$ Oct 27, 2015 at 16:09
  • 1
    $\begingroup$ @MichaelChirico I guess "appartains at $N$" is an attempt to translate appartient à $N$, which is French for belongs to $\mathbb{N}$. $\endgroup$
    – yoann
    Oct 27, 2015 at 20:55
  • $\begingroup$ @yoann neat! $N$ instead of $\mathbb{N}$ threw me off the scent of that possibility. $\endgroup$ Oct 27, 2015 at 21:51

4 Answers 4

8
$\begingroup$

Your inductive assumption is such that the formula marked $\color{red}{\mathrm{red}}$ (several lines below) holds for $i=k$: $$\sum^{i=k}_{i=1} i^3=\frac{k^2 (k+1)^2}{4}$$

You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^3=\color{blue}{\frac{(k+1)^2 (k+2)^2}{4}}$$ To do this you cannot use: $$\sum^{i=n}_{i=1} i^3=\color{red}{\frac{n^2 (n+1)^2}{4}}$$ as this is what you are trying to prove.

So what you do instead is notice that: $$\sum^{i=k+1}_{i=1} i^3= \underbrace{\frac{k^2 (k+1)^2}{4}}_{\text{sum of k terms}} + \underbrace{(k+1)^3}_{\text{(k+1)th term}}$$ $$\sum^{i=k+1}_{i=1} i^3= (k+1)^2\left(\frac{1}{4}k^2+(k+1)\right)$$ $$\sum^{i=k+1}_{i=1} i^3= (k+1)^2\left(\frac{k^2+4k+4}{4}\right)$$ $$\sum^{i=k+1}_{i=1} i^3= (k+1)^2\left(\frac{(k+2)^2}{4}\right)=\color{blue}{\frac{(k+1)^2 (k+2)^2}{4}}$$

Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.

$\endgroup$
6
  • $\begingroup$ @Alwayslearning Good to see you making a positive start with inductive techniques, well done. I have added something of my own here, I was a little late for the party, and I think the other users have already given you some good answers. $\endgroup$
    – BLAZE
    Oct 27, 2015 at 13:03
  • 1
    $\begingroup$ Yes, I have understood it already but your answer is very precise and well written and targets exactly what was my doubt! However, I am just writing another question about another proof by induction;) $\endgroup$ Oct 27, 2015 at 13:13
  • $\begingroup$ @Alwayslearning Thank you, that means a lot; basically your logic was totally correct when you asked "perhaps we do it by showing that after algebraic passages $\frac{k^2(k+1)^2 }{4} + (k+1)^3$ is equal to $\frac{(k+1)^2[(k+1)+1]^2}{4}$?" You were right with that approach, you need to have more confidence in your ability. Well spotted :) $\endgroup$
    – BLAZE
    Oct 27, 2015 at 13:16
  • 1
    $\begingroup$ To me this seems rather unfortunate to say that some formula holds for $i=k$, when the formula does not contain $i$ as a free variable, but as index of summation. $\endgroup$ Nov 30, 2015 at 11:41
  • $\begingroup$ @Martin Sorry it took me so long to reply. By "unfortunate", I'm guessing you mean 'sub-optimal' or maybe even 'incorrect'. I think understand what you are saying about referring to summation index as if it was a variable in a formula. This does seem a little odd, but I simply could not think of any other way to word it more appropriately, and even more unfortunate is that this is the way I have seen induction techniques written in textbooks. Do you have any recommendations on an improved way of wording this? Thanks for pointing this out, I appreciate that. $\endgroup$
    – BLAZE
    Dec 11, 2015 at 7:47
6
$\begingroup$

It seems your issue is more conceptual than algebraic since you're stuck about which form of right hand side to use.

A proof by induction on a sum formula works by showing: (1) it holds in the base case, when the index is at its minimum; and (2) if it applies for the $n=k$ case, then it will also hold for the $n=k+1$ case.

With these two in hand we prove that the formula holds at any index. For example, we know it holds at $k=10$ because it holds at $k=1$ (via (1)) which implies it holds at $k=2$ (via (2)) which implies it holds at $k=3$ (via (2) again), and so on, repeatedly applying (2) until we reach 10.

We want to show that "the formula applies at $k$" implies that the formula holds at $k+1$, so our target is showing that $\sum_{i=1}^{k+1}i^3 = \frac{(k+1)^2((k+1)+1)^2}{4}$ and our ammunition is our assumption that $1^3+\ldots+k^3=\frac{k^2(k+1)^2}{4}$.

To connect the two, we notice that the left side of our target nests our assumption -- $\sum_{i=1}^{k+1}i^3 = (1^3+\ldots+k^3)+(k+1)^3$.

The rest is algebra.

$\endgroup$
3
  • $\begingroup$ I think I have clarified all my doubts with this question! $\endgroup$ Oct 27, 2015 at 12:38
  • $\begingroup$ @Michael Was it you who had the answer accepted first? In any case I felt bad as my answers in the past have been accepted then unaccepted so I know how it feels. So to counter this I have up-voted all answers in this thread (+1 for all) $\endgroup$
    – BLAZE
    Oct 27, 2015 at 14:09
  • 2
    $\begingroup$ @BLAZE it wasn't, and thanks for the upvote, but the best answer should always get the tick. and yours is colorful! :p $\endgroup$ Oct 27, 2015 at 14:58
3
$\begingroup$

You should use the second one: Suppose it holds for the first $k$ numbers. So their sum is equal to $\frac{k²(k+1)^2}{4}$. Then the first sum of the first $k+1$ is equal to $1^3 + 2^3 + 3^3 + ... + (k+1)^3=\frac{k²(k+1)^2}{4}+(k+1)^3=\frac{k²(k+1)^2}{4}+\frac{4(k+1)^3}{4}$ which is equal to $\frac{k²(k+1)^2+4(k+1)^3}{4}=\frac{(k+1)²(k²+4k+4)}{4}=\frac{(k+1)²(k+2)²}{4}$.

Which is precisely what you need.

$\endgroup$
4
  • $\begingroup$ Thank you! But, perhaps, you could break your passages as the final ones go on the right column of the website where there are the related questions. Thus, I can't read all your passages. $\endgroup$ Oct 27, 2015 at 11:34
  • $\begingroup$ Does this help? $\endgroup$
    – Biouk
    Oct 27, 2015 at 11:37
  • $\begingroup$ yes, thanks. Now it is the other answer which goes on the right side of the website:) but it is written in big characters, so I can read it ;) Thank you both! I am looking at the algebraic passages in order to be sure that everything is clear to me. $\endgroup$ Oct 27, 2015 at 11:42
  • $\begingroup$ After your final step, in order to make the sentence similar to the original one, I would write (k+1)^2 * [(k+1)+1]^2 / 4 thank you! $\endgroup$ Oct 27, 2015 at 12:08
2
$\begingroup$

You want to prove that $$\sum_{i=1}^{n}i^3 = \frac{n^2 (n+1)^2}{4}$$ using induction.

For $n=1$, $$\sum_{i=1}^{1}i^3 = 1^3=1=\frac{1^2(1+1)^2}4=1$$ So the formula does work for the base case $n=1$.

Now, assume the formula works for $n=k$ and show that this implies that the formula is correct for $n=k+1$ which will accomplish the prove by induction. Thus, \begin{align} \sum_{i=1}^{k+1}i^3 & = \left(\sum_{i=1}^{k}i^3\right) +(k+1)^3 \\ & = \frac{k^2 (k+1)^2}{4}+(k+1)^3 \\ & = \frac{k^2 (k+1)^2+4(k+1)^3}{4} \\ & = \frac{ (k+1)^2(k^2+4(k+1))}{4} \\ & = \frac{ (k+1)^2(k+2)^2}{4} \\ & = \frac{ (k+1)^2((k+1)+1)^2}{4} \end{align} and you are done.

$\endgroup$
1
  • $\begingroup$ Thak you! But the final number is 1, not 2, I think! $\endgroup$ Oct 27, 2015 at 12:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .