Induction Question!!!

**Chuck_3000** · June 15th 2007, 04:13 AM

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?

**Pterid** · June 15th 2007, 04:45 AM

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

**topsquark** · June 15th 2007, 05:20 AM

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

-Dan

**topsquark** · June 15th 2007, 05:29 AM

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

**CaptainBlack** · June 15th 2007, 05:55 AM

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

**Soroban** · June 15th 2007, 07:00 AM

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.

**topsquark** · June 15th 2007, 07:14 AM

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

ActionBallMan · June 15th 2007, 08:05 PM

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!

**Jhevon** · June 15th 2007, 08:28 PM

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?

**Jhevon** · June 15th 2007, 08:42 PM

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

**CaptainBlack** · June 15th 2007, 09:42 PM

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

**Jhevon** · June 15th 2007, 09:51 PM

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

Thread: Induction Question!!!

LinkBack

Thread Tools

Display

Induction Question!!!

Hi im new here :)

Similar Math Help Forum Discussions

Induction question

Induction question

induction question..

Question on induction

induction question

Search Tags