1. ## Induction Question!!!

can anyone help with this induction problem:

n³ = ¼ n² (n+1)²

i'm having trouble proving true for n = k+1

i need to prove that (k+1)³ = ¼ (k+1)² (k+2)² (i hope this is right)

by assumption the LHS should be ¼ k² (k+1)² (k+1) is it not?

can someone help me as to solving this?

2. This identity should be very hard to prove - because it's not true!

Counterexample: consider $n = 10$.

$n^3 = 1000;$
$\frac{1}{4} n^2 (n+1)^2 = \frac{10^2 \cdot 11^2}{4} = 3025.$

3. I believe the expression should be:
$\sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2$

-Dan

4. Originally Posted by topsquark
I believe the expression should be:
$\sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2$

-Dan
Let n = 1:
Then
$\sum_{k = 1}^1k^3 = 1$
$\frac{1}{4}1^2(1 + 1)^2 = 1$ (Check!)

So assume this is true for some value of n. We need to show it is true for n + 1. That is, assume
$\sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2$

We need to show this for
$\sum_{k = 1}^{n+ 1}k^3 = \frac{1}{4}(n+ 1)^2(n+ 2)^2$

Well,
$\sum_{k = 1}^{n+ 1}k^3 = \sum_{k = 1}^nk^3 + (n + 1)^3$

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

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

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

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

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

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

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

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

$= \sum_{k = 1}^nk^3 + (n + 1)^3$

as required.

-Dan

5. Originally Posted by CaptainBlack
What you mean is prove:

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

RonL
If this is true for $n=k$, then:

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

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

Which completes the inductive step and the rest is plain sailing.

RonL

6. Hello, Chuck!

Prove by induction: . $\sum^n_{i=1} i^3 \:=\:\frac{n^2(n+1)^2}{4}$
You've already verified $S(1)$, right?

We assume $S(k)$ is true: . $1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}$

Add $(k+1)^3$ to both sides:
. . $\underbrace{1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3} \;=\;\frac{k^2(x+1)^2}{4} + (k+1)^3$
. . The left side is the left side of $S(k+1).$

Factor the right side: . $(k+1)^2\left[\frac{k^2}{4} + (k+1)\right] \;=\;(k+1)^2\left[\frac{k^2+4k+4}{4}\right] \;=\;\frac{(k+1)^2(k+2)^2}{4}$
. . This is the right side of $S(k+1).$

Therefore, we have: . $1^3+ 2^3 + 3^3 + \cdots + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}$
. . and the inductive proof is complete.

7. Originally Posted by Soroban
Hello, Chuck!

You've already verified $S(1)$, right?

We assume $S(k)$ is true: . $1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}$

Add $(k+1)^3$ to both sides:
. . $\underbrace{1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3} \;=\;\frac{k^2(x+1)^2}{4} + (k+1)^3$
. . The left side is the left side of $S(k+1).$

Factor the right side: . $(k+1)^2\left[\frac{k^2}{4} + (k+1)\right] \;=\;(k+1)^2\left[\frac{k^2+4k+4}{4}\right] \;=\;\frac{(k+1)^2(k+2)^2}{4}$
. . This is the right side of $S(k+1).$

Therefore, we have: . $1^3+ 2^3 + 3^3 + \cdots + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}$
. . and the inductive proof is complete.

Aw shucks! That was the easy way to do it! (I figured there had to be one...)

-Dan

8. ## Hi im new here :)

I was going to start a new thread but I decided to tagg along this one. Okay I have two problems. Please explain this clearly. Im really having a hard time understanding this stuff.

Prove by induction that for any x, if x 1, then 3n 1 + 2n.
Step 1:For x =, P() = [(3 × 1) = 1 + 2].The base case is (Type T/F.).Step 2:For k suppose that 3k 1 + 2k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 + 2(k + 1)This becomes3k + (1 + 2) + 2We conclude the statement is(Type T/F.)because the left side increases more than the right.

Prove by induction that for any x, if x 1, then 5n 1 + 4n .
Step 1:For x = 1, P(1) = [(5 × 1) = 1 +].The base case is (Type T/F.).Step 2:For k suppose that 5k 1 + 4k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 +(k + 1)This becomes5k + (1 + 4) + 4We conclude the statement is (Type T/F.)because the left side increases more than the right.

Thank You!

9. Originally Posted by ActionBallMan
I was going to start a new thread but I decided to tagg along this one. Okay I have two problems. Please explain this clearly. Im really having a hard time understanding this stuff.

Prove by induction that for any x, if x 1, then 3n 1 + 2n.
Step 1:For x =, P() = [(3 × 1) = 1 + 2].The base case is (Type T/F.).Step 2:For k suppose that 3k 1 + 2k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 + 2(k + 1)This becomes3k + (1 + 2) + 2We conclude the statement is(Type T/F.)because the left side increases more than the right.

Prove by induction that for any x, if x 1, then 5n 1 + 4n .
Step 1:For x = 1, P(1) = [(5 × 1) = 1 +].The base case is (Type T/F.).Step 2:For k suppose that 5k 1 + 4k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 +(k + 1)This becomes5k + (1 + 4) + 4We conclude the statement is (Type T/F.)because the left side increases more than the right.

Thank You!
are these your proofs, or were they given to you and you're trying to understand them? there seems to be some stuff missing. do you understand the general method of proving things by induction?

10. Originally Posted by ActionBallMan
Prove by induction that for any x, if x 1, then 3x 1 + 2x.
ok, so first of all, you had different variables, everything must be in one variable. you cant make a statement about x and then prove something about n when we don't know anything about n. i changed everything to x. Here's how i would do them

Let P(x): "If $x \geq 1$, then $3x \geq 1 + 2x$ for all integers $x$"

We have for the base case:

P(1): $3(1) = 3 \geq 1 + 2(1) = 3$, so P(1) is true

Assume P(k) is true for some k $\geq$ 1. We show that P(k + 1) is true

Since P(k) is true, we have:

$3k \geq 1 + 2k$

It follows that:

$3 k + 3 \geq 1 + 2k + 2$, since we add 3 to the left and 2 to the right

But we can factor this so that:

$3(k + 1) \geq 1 + 2(k + 1)$ which is P(k + 1)

Thus the inductive proof is complete and P(x) holds true for all integers x $\geq$ 1

Prove by induction that for any n, if n 1, then 5n 1 + 4n .
This one is pretty much the same as the last.

Let P(n): "If $n \geq 1$, then $5n \geq 1 + 4n$ for all integers $n$"

So P(1): $5(1) = 5 \geq 1 + 4(1) = 5$. So P(1) is true

Assume P(k) true for some k $\geq$ 1, we show that P(k + 1) is true

Since P(k) is true, we have:

$5k \geq 1 + 4k$

It follows that:

$5k + 5 \geq 1 + 4k + 4$

Factoring we get:

$5(k + 1) \geq 1 + 4(k + 1)$, which is P(k + 1)

Thus the inductive proof is complete, and P(n) holds for all integers n $\geq$ 1

11. Originally Posted by Jhevon
ok, so first of all, you had different variables, everything must be in one variable. you cant make a statement about x and then prove something about n when we don't know anything about n. i changed everything to x. Here's how i would do them

Let P(x): "If $x \geq 1$, then $3n \geq 1 + 2n$"

We have for the base case:

P(1): $3(1) = 3 \geq 1 + 2(1) = 3$, so P(1) is true

Assume P(k) is true for some k $\geq$ 1. We show that P(k + 1) is true

Since P(k) is true, we have:

$3k \geq 1 + 2k$

It follows that:

$3 k + 3 \geq 1 + 2k + 2$, since we add 3 to the left and 2 to the right

But we can factor this so that:

$3(k + 1) \geq 1 + 2(k + 1)$ which is P(k + 1)

Thus the inductive proof is complete and P(x) holds true for all x $\geq$ 1

This one is pretty much the same as the last.

Let P(n): "If $n \geq 1$, then $5n \geq 1 + 4n$"

So P(1): $5(1) = 5 \geq 1 + 4(1) = 5$. So P(1) is true

Assume P(k) true for some k $\geq$ 1, we show that P(k + 1) is true

Since P(k) is true, we have:

$5k \geq 1 + 4k$

It follows that:

$5k + 5 \geq 1 + 4k + 4$

Factoring we get:

$5(k + 1) \geq 1 + 4(k + 1)$, which is P(k + 1)

Thus the inductive proof is complete, and P(n) holds for all n $\geq$ 1

There is a flaw in the statement of the problem, and what you have proven
(lets forget the mixtue of [tex]x[tex]'s and $n$'n for the moment)

Induction in the form used will only prove these statments for all
integers $n \ge 1$, or whatever, not for all $n$ in some unspecified set.

RonL

12. Originally Posted by CaptainBlack
There is a flaw in the statement of the problem, and what you have proven
(lets forget the mixtue of [tex]x[tex]'s and $n$'n for the moment)

Induction in the form used will only prove these statments for all
integers $n \ge 1$, or whatever, not for all $n$ in some unspecified set.

RonL
yes, you are right. i was thinking about intergers though, just neglected to say it. I changed it