# Thread: Inductive Step...Confused when solving this equation?

1. ## Inductive Step...Confused when solving this equation?

Its part e I am stuck on

Q: Let P(n) be the statement that 1^3 + 2^3 +….n^3 = (n(n + 1) / 2)² for the positive
integer n.

a.) What is the statement P(1)?
b.) Show that P(1), completing the basis step of the proof?
c.) What is the Inductive Hypothesis?
d.) What do you need to prove in the Inductive Step?
e.) Complete the inductive Step?
f.) Explain why these steps show that the formula is true whenever n is a positive integer?
__________________________________________________ ______________________________________________
A:
a.) P(n) = (n(n + 1) / 2)²
P(1) = (1(1 + 1) / 2)²
= (2 / 2)²
= 1
b.) Basis Step:
we will let n = 1
n^3 = (n(n + 1) / 2)²
1^3 = (1(1 + 1) / 2)²
1 = (2 / 2)²
1 = 1
Since both are equal, the basis step hold.
c.) Inductive Hypothesis:
This is the statement 1^3 + 2^3 +….k^3 = (k(k + 1) / 2)²
d.) I have to prove that k > 1 and P(k) implies P(k + 1).
Or.
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)²
1^3 + 2^3 +….k^3 + (k + 1)^3 = (((k + 1)((k + 2)) / 2)²

e.)
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)² + (k + 1)
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)² · ((k + 2)²) / 4 + (k + 1)
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)² · (k + 2))² + 4(k + 1)

2. You need to show that 1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)²

now

$1^3 + 2^3 +….k^3 + (k + 1)^3$
$= (k(k+1)/2)^2 + (k +1 )^3$

$= (k+1)^2 ( k^2/4 + k +1)$
$= (k + 1)^2(k^2 + 4k + 4)/2$
$= (k + 1)^2 (k + 2)^2 /4$
$= ((k + 1)(k + 2)/2)^2$

Hence P(k+1) is proved true.

Do you need an explanation of part f?

3. the inductive step is all about using your hypothesis that P(k) is true and show that this implies that P(k+1) is true.

So $1^{3} + 2^{3} + ... + k^{3} + (k + 1)^{3}$ = $( \frac {k (k + 1)} {2})^2 + (k + 1)^{3}$ has to be rearranged so as to show that it equal $(\frac {(k+1)(k+2)} {2})^2$

and I see arpitagarwal beat me to it

4. Originally Posted by arpitagarwal82
You need to show that 1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)²

now

$1^3 + 2^3 +….k^3 + (k + 1)^3$
$= (k(k+1)/2)^2 + (k +1 )^3$

$= (k+1)^2 ( k^2/4 + k +1)$
$= (k + 1)^2(k^2 + 4k + 4)/2$
$= (k + 1)^2 (k + 2)^2 /4$
$= ((k + 1)(k + 2)/2)^2$

Hence P(k+1) is proved true.

Do you need an explanation of part f?
that would be helpful with part f.

So what your saying, is you take the formula (LHS only) and break it down into the formula you trying to prove in the inductive step. But with the regular formula, you replace n with k. Is that correct?

5. Originally Posted by nmatthies1
the inductive step is all about using your hypothesis that P(k) is true and show that this implies that P(k+1) is true.

So $1^3 + 2^{3} + … + k^{3} + (k + 1)^{3}$ = $( \frac {k (k + 1)} {2})^2 + (k + 1)^{3}$ has to be rearranged so as to show that it equal $(\frac {(k+1)(k+2)} {2})^2$

and I see arpitagarwal beat me to it
hey, any help is appreciated. Thank you also :P

6. As per process of induction, we have assumed that P(k) is true.
so we have
1^3 + 2^3 +….k^3 + = (k (k + 1) / 2)² ------ eq1

Now we have to prove that P(k+1 ) is true.
that means we have to prove
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)²

we have taken the LHS side of above.
then we have used eq1 and simplified the LHS to show that its equal to RHS.
hence we have proved that P(k+1) is true.
Is that clear now?
Now try to explain part f of question. And let us know if you have problem with that.

7. Originally Posted by arpitagarwal82
As per process of induction, we have assumed that P(k) is true.
so we have
1^3 + 2^3 +….k^3 + = (k (k + 1) / 2)² ------ eq1

Now we have to prove that P(k+1 ) is true.
that means we have to prove
1^3 + 2^3 +….k^3 + (k + 1)^3 = ((k + 1)((k + 1) + 1) / 2)²

we have taken the LHS side of above.
then we have used eq1 and simplified the LHS to show that its equal to RHS.
hence we have proved that P(k+1) is true.
Is that clear now?
Now try to explain part f of question. And let us know if you have problem with that.
arpitagarwal82 for part f, is this correct:

This shows that if P(n) is true and P(n + 1) is true, then the equation: 1^3 + 2^3 +….n^3 = (n(n + 1) / 2)² is true for all positive integers of n..

8. You have shown that $P(1)$ is true and $P(n) true \rightarrow P(n+1) true$ and so $P(1) true \rightarrow P(2) true$ , $P(2) true \rightarrow P(3) true$ and so on.

9. thanks nmathies....

thank you arpitagarwal82.

I am starting to understand this alittle bit more. I am going to do some more sample problems and get a better feel for this

10. yes that's the only way to learn to do maths! if you have any more problems just ask

11. Originally Posted by nmatthies1
yes that's the only way to learn to do maths! if you have any more problems just ask
I will definitely. He started covering these tuesday, but was so quick its hard to get a grasp. Discrete math aint my thing. I prefer the usual, Differential equations, Calculus, Algebra,...those. Discrete, is not what I would call math.

12. yes most people like the more tangible stuff but when you think about it maths wouldn't be very far without proofs!! it is one of the most important things in the study of mathematics and that is why university mathematics puts the focus on it.

13. Originally Posted by nmatthies1
yes most people like the more tangible stuff but when you think about it maths wouldn't be very far without proofs!! it is one of the most important things in the study of mathematics and that is why university mathematics puts the focus on it.
Thats true

14. When doing problems that tends to these 3 steps: Basis Step, Inductive Hypothesis and proving the Inductive Step, I am having difficuly understanding the Inductive Hypotheses. I understand you switch n with (k + 1) but for the prvious problem we added the (k + 1)^3 to the LHS and RHS? How do you know to do that. just like in this problem below:

Q: Prove that 1 · 1! + 2 · 2! + ··· n · n! = (n + 1)! – 1 whenever n is a positive integer?

I have this:
Basis step:
Let n = 1
n · n! = (n + 1)! – 1
1 · 1! = (1 + 1)! – 1
1 · 1 = (2)! – 1
1 = 1
Since they both equal, the basis step holds.
Inductive Hypothesis:
1 · 1! + 2 · 2! + ··· (k + 1) · (k + 1)! = ((k + 1) + 1)! – 1

Would I add a (k + 2)! to both the LHS and RHS?

15. I think you are very clear with base case. Only conusion is inductive hypothesis and proof.

So here is a bit exlaination.

First we have to assume that statement is true for any number say k, and then we have to prove that statement is correct for next consecutive number k+1.
So if you assume that statement is true for k+1, prove that its correct for k+2.
OR
If you assume that statement is true for k-1, prove tat its true for k

Or similar.

In the first (post 1 of this thread)
we have to prove that 1^3 + 2^3 +….n^3 = (n(n + 1) / 2)²

we have assumed it correct for k.

so we have now
1^3 + 2^3 +….k^3 = (k(k + 1) / 2)² -----------eq1
i.e sum of cube of numbers from 1 to k is (k(k+1)/2)^2

Now we have to prove that statement is true for k+1.
so what do we have to prove?
sum of cubes of number from 1 to k+1 is ((k+1)(k+1+1)/2)^2

Got it?

Now use this sameapproch for any question.

Like in above problem 1! + 2 · 2! + ··· n · n! = (n + 1)! – 1

assume it true for k
so we have assumed 1! + 2 · 2! + ··· k · k! = (k + 1)! – 1

now prove for k+1

Page 1 of 2 12 Last