1
$\begingroup$

Use mathematical induction to prove each of the following statements. let $$g(n) = 1^3 + 2^3 + 3^3 + ... + n^3$$

Show that the function $$g(n)= \frac{n^2(n+1)^2}{4}$$ for all n in N

so the base case is just g(1) right? so the answer for the base case is 1, because 4/4 = 1

then for g(2) is it replace all of the n's with n + 1 and see if there is a concrete answer?

$\endgroup$
  • $\begingroup$ A concrete answer to what? Your question isn't clear. Are you asking if the inductive step is to assume that $g(n) = \frac{n^2(n+1)^2}{4}$, and then use that to evaluate g(n+1)? $\endgroup$ – prokaryoticeukaryote Dec 12 '16 at 17:21
  • $\begingroup$ You now want to assume that the formula holds for $n=k $, and have to show that the formula holds for $n=k+1$. $\endgroup$ – Dave Dec 12 '16 at 17:21
  • $\begingroup$ proofwiki.org/wiki/Sum_of_Sequence_of_Cubes/Proof_by_Induction $\endgroup$ – rlartiga Dec 12 '16 at 17:23
  • $\begingroup$ @Dave So i have to show that g(n) = that equation for all n in N. Do i just do so by doing k+1 in place of every n for different values? so for instance, answer the equation once where k = 2 and then again where k =3 and so on? $\endgroup$ – Jim Derkin Dec 12 '16 at 17:25
  • $\begingroup$ barak manos' answer is exactly what I meant. If you show the formula is true for $n=1,2,3,... $ that would literally take you forever, or eventually you'd stop, and then the proof isn't very rigorous. See the answer below for the proper induction method. $\endgroup$ – Dave Dec 12 '16 at 17:29
2
$\begingroup$

First, show that this is true for $n=1$:

$\sum\limits_{k=1}^{1}k^3=\frac{1^2(1+1)^2}{4}$

Second, assume that this is true for $n$:

$\sum\limits_{k=1}^{n}k^3=\frac{n^2(n+1)^2}{4}$

Third, prove that this is true for $n+1$:

$\sum\limits_{k=1}^{n+1}k^3=$

$\color\red{\sum\limits_{k=1}^{n}k^3}+(n+1)^3=$

$\color\red{\frac{n^2(n+1)^2}{4}}+(n+1)^3=$

$\frac{(n+1)^2(n+1+1)^2}{4}$


Please note that the assumption is used only in the part marked red.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the second, we say: let $n\geq1$ be such that :. $\endgroup$ – hamam_Abdallah Dec 12 '16 at 17:29
  • $\begingroup$ This is great, finally see what I have to do for it. thanks! $\endgroup$ – Jim Derkin Dec 12 '16 at 17:34
  • $\begingroup$ @Jim: You're welcome :) $\endgroup$ – barak manos Dec 12 '16 at 17:34
  • $\begingroup$ @barakmanos sorry, I just want to make sure i'm doing this right for other questions. i have a \sum\limits_{j=1}^{n}= \frac{1}{n(n+1)} and have to show that \frac{n}{n+1} applies for all n in N. so it's the same setup right? where i do the n =1. then assume that it's true for n and prove that its true for n + 1 by simply saying \frac{n+1}{n+2} right? $\endgroup$ – Jim Derkin Dec 12 '16 at 18:08
  • $\begingroup$ @Jim: This comment is unreadable. Please post it as a separate question (and don't forget to embrace each LaTex expression with a pair of dollars). $\endgroup$ – barak manos Dec 12 '16 at 18:18
0
$\begingroup$

Hint: Think of what you are supposed to prove: That a property $P(n)$ is true for every natural number.

A proof by induction essentially proves that the property $P(n)$ holds for the first natural number and is preserved, as we count upwards.

In this case the property $P(n)$ is

$$P(n) \text{ is true if } g(n) = \frac{n^2(n+1)^2}{4}$$

The base case consists of proving that the property $P(1)$ is true, that is, that

$$g(1) = \frac{1^2(1+1)^2}{4}$$

In the inductive step you must prove that if $P(n)$ is true, then so is $P(n+1)$.

Now what does it mean that $P(n+1)$ is true?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You want to show that $$\sum_{j=1}^n j^3 = \frac{n^2(n+1)^2}{4}.$$

You've shown that it holds for the base case, which is good.

Now, you assume that it holds for $n=k$:

$$\sum_{j=1}^k j^3 = \frac{k^2(k+1)^2}{4}.$$

Then, a strategy is to write out one part or the other for the $n=k+1$ case, and manipulate it so that you pull out the $n=k$ expression. Let's do the sum:

$$\sum_{j=1}^{k+1} j^3 = \sum_{j=1}^{k} j^3 + (k+1)^3.$$

This is just algebra; I pulled out the last term and wrote it explicitly. But now I can substitute in the assumption for the sum on the right hand side.

The rest is to manipulate the expression on the right hand side to come up with the expression

$$\frac{(k+1)^2(k+2)^2}{4},$$

and then you're done.

Can you take it from here?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Show that: $$1^3 + 2^3 + 3^3 + ... + n^3= \frac{n^2(n+1)^2}{4}$$


$(1)$ First step is to evaluate the expression for $n=1$, $$1^3=\frac{1\times(1+1)^2}{4}$$ Which is $1=1$, which means we can proceed.


$(2)$ Now assume it is true for $n$, $$1^3 + 2^3 + 3^3 + ... + n^3= \frac{n^2(n+1)^2}{4}$$


$(3)$ Lastly prove for $n+1$ and you have proved it for all $n\in\mathbb N$,

$$1^3 + 2^3 + 3^3 + ... +n^3+ (n+1)^3= \frac{(n+1)^2(n+2)^2}{4}$$

After "inserting" $n+1$, replace the left side as it follows:

$$ \frac{n^2(n+1)^2}{4}+(n+1)^3=\frac{(n+1)^2(n+2)^2}{4}$$

Simply "tidy up" the left side to get the final form;

$$\frac{(n+1)^2(n+2)^2}{4}=\frac{(n+1)^2(n+2)^2}{4}$$


And that's an example of a proof with induction.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Base Case:

Show that $g(n)$ holds for $n=1$.

(You've done this already).


Inductive Hypothesis:

Assume that $g(n)$ holds for arbitrary $k \in \mathbb{N}$, where $k \geq 1$ (since you already proved base case).

Thus we have that:

$$g(k) = \frac{k^2(k+1)^2}{4}$$


Inductive Step:

Show that $g(k) \to g(k+1)$

$$g(k+1) = \frac{(k+1)^2((k+1)+1)^2}{4} = \frac{(k+1)^2(k+2)^2}{4}$$

Notice that if we expand $g(k+1)$, we get: $$\frac{\left(k^4+6k^3+13k^2+12k+4\right)}{4}$$

Now for the proof:

We know that $g(k+1) = g(k) + (k+1)^3$

We can assume $g(k)$ holds via our inductive hypothesis.

Thus we have:

$$g(k+1) = g(k) + (k+1)^3$$ $$g(k+1) = \frac{k^2(k+1)^2}{4} + (k+1)^3$$ $$g(k+1) = \frac{k^2(k+1)^2}{4} + \frac{4(k+1)^3}{4}$$

After you simplify and collect like terms, you will end up with $g(k+1)$ (this is why I expanded the original equation for $g(k+1)$ so we don't have to factor anything hard.

QED.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Assuming you are asking what the inductive step is, you simply need to assume that $g(n) =\frac{n^2(n+1)^2}{4}$ and then use it to evaluate g(n+1) like so: \begin{equation} g(n+1) = g(n) + (n+1)^3 \end{equation} \begin{equation} g(n+1) = \frac{n^2(n+1)^2}{4} + (n+1)^3 \end{equation} \begin{equation} g(n+1) = \frac{4(n+1)^3 + n^2(n+1)^2}{4} \end{equation} \begin{equation} g(n+1) = \frac{(n+1)^2(4(n+1) + n^2)}{4} \end{equation} \begin{equation} g(n+1) = \frac{(n+1)^2(n^2 + 4n + 4)}{4} \end{equation} \begin{equation} g(n+1) = \frac{(n+1)^2(n+2)^2}{4} \end{equation}

Q.E.D.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.