induction help

**jvignacio** · April 19th 2010, 01:42 AM

Hey guys, im really struggling with induction. Question: Use induction to prove that 1 + 7 + 19 +..... + ( $3n^2 - 3n + 1$ ) = $n^3$ for all positive integers $n$ by completing the following steps:

a) Show that the statement is true when $n=1$ .

My answer: Is this just substituting $n=1$ into $3n^2 - 3n + 1$ ? and how do I know its true?

b) show that, if 1 + 7 + 19 + .... + ( $3k^2 - 3k + 1$ ) = $k^3$ , then 1 + 3 + 5 + ... + ( $3k^2 - 3k + 1$ ) + $(3(k + 1)^2 -3(k + 1) +1$ ) = $(k+1)^3$ .

my answer: Not sure this one! Any help would be much appreciated.

**BabyMilo** · April 19th 2010, 02:53 AM

Sorry this is wrong. O.o

**Archie Meade** · April 19th 2010, 03:04 AM

Originally Posted by jvignacio

Hey guys, im really struggling with induction. Question: Use induction to prove that 1 + 7 + 19 +..... + ( $3n^2 - 3n + 1$ ) = $n^3$ for all positive integers $n$ by completing the following steps:

a) Show that the statement is true when $n=1$ .

My answer: Is this just substituting $n=1$ into $3n^2 - 3n + 1$ ? and how do I know its true?

Yes, just check that if you set n=1 on both sides of the equality, then they are equal

n=1, 3(1)(1)-3(1)+1=3-3+1=1
1=1(1)1...true for n=1

b) show that, if 1 + 7 + 19 + .... + ( $3k^2 - 3k + 1$ ) = $k^3$ , then 1 + 3 + 5 + ... + ( $3k^2 - 3k + 1$ ) + $(3(k + 1)^2 -3(k + 1) +1$ ) = $(k+1)^3$ .

my answer: Not sure this one! Any help would be much appreciated.

Part b) attempts to show that if the statement is true for some n=k,
then being true for n=k causes the statement to be true for the next n,
which is n=k+1.

The purpose of this is to show that...

true for n=1 causes the equality to be true for n=2,
true for n=2 causes the equality to be true for n=3,
true for n=3 causes the equality to be true for n=4....
all the way to infinity

then you can see by thinking about it that an infinite chain of cause and effect
has been set up between adjacent terms.

Hence we express the k+1 version in terms of the k version
to see if there is a cause and effect relationship.

Essentially, this is why part b) is written as it is.

$1+7+19+...+(3k^2-3k+1)=k^3$ ?

If it is then examining

$1+7+19+...(3k^2-3k+1)+\left[3(k+1)^2-3(k+1)+1\right]$

which is the sum of (k+1) terms,

and examining if this is $(k+1)^3$ if the sum of k terms is $k^3,$ we get

$k^3+3(k+1)^2-3(k+1)+1=k^3+3(k^2+2k+1)-3(k+1)+1$

$=k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1$

which is $(k+1)^3,$ since

$(k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$ $=k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1$

Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

Therefore there is an infinite chain of cause and effect.
If the equality is true for n=1, this causes the equality to be true for all n.

**jvignacio** · April 19th 2010, 03:11 AM

Originally Posted by BabyMilo

$3n^2-3n+1$ does not = $n^3$

try when n=2 rather than n=1
you will see LHS=7 while RHS=8

if you do step two to prove it,
you will find LHS= $k^3+k+1$ , while RHS= $k^3+3k^2+3k+1$

Hope this helps!

for a) shouldnt it be $LHS = 1$ , $RHS = n^3 = 1^3 = 1$ , therefore true for $n=1$ ?

**jvignacio** · April 19th 2010, 03:17 AM

Originally Posted by Archie Meade

Part b) attempts to show that if the statement is true for some n=k,
then being true for n=k causes the statement to be true for the next n,
which is n=k+1.

The purpose of this is to show that...

true for n=1 causes the equality to be true for n=2,
true for n=2 causes the equality to be true for n=3,
true for n=3 causes the equality to be true for n=4....
all the way to infinity

then you can see by thinking about it that an infinite chain of cause and effect
has been set up between adjacent terms.

Hence we express the k+1 version in terms of the k version
to see if there is a cause and effect relationship.

Essentially, this is why part b) is written as it is.

$1+7+19+...+(3k^2-3k+1)=k^3$ ?

If it is then examining

$1+7+19+...(3k^2-3k+1)+\left[3(k+1)^2-3(k+1)+1\right]$

which is the sum of (k+1) terms,

and examining if this is $(k+1)^3$ if the sum of k terms is $k^3,$ we get

$k^3+3(k+1)^2-3(k+1)+1=k^3+3(k^2+2k+1)-3(k+1)+1$

$=k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1$

which is $(k+1)^3,$ since

$(k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$ $=k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1$

Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

Therefore there is an infinite chain of cause and effect.
If the equality is true for n=1, this causes the equality to be true for all n.

For a) do I substitute n=1 into $n^3$ OR $3n^2 - 3n + 1$

**Archie Meade** · April 19th 2010, 03:25 AM

Originally Posted by jvignacio

For a) do I substitute n=1 into $n^3$ OR $3n^2 - 3n + 1$

Hi jvignacio,

you must substitute n=1 into both

for it is the same n on both sides.

You see, all those earlier terms are $3n^2-3n+1$

with n=1, 2, 3 etc

Hence, putting n=1, we have only the first term (it doesn't add to anything).

$3(1)^2-3(1)+1=1$

$3(2)^2-3(2)+1=12-6+1=7$

$3(3)^2-3(3)+1=27-9+1=19$ etc

The $n^3$ is the sum of these

$1=1^3$

$1+7=2^3$

$1+7+19=3^3$ etc

**jvignacio** · April 19th 2010, 05:13 AM

Originally Posted by Archie Meade

and examining if this is $(k+1)^3$ if the sum of k terms is $k^3,$ we get

$k^3+3(k+1)^2-3(k+1)+1=k^3+3(k^2+2k+1)-3(k+1)+1$

$=k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1$

which is $(k+1)^3,$ since

$(k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$ $=k^3+k^2+2k^2+2k+k+1=k^3+3k^2+3k+1$

Hence, the equality being true for some term n=k causes the equality to be true for the next term n=k+1.

Therefore there is an infinite chain of cause and effect.
If the equality is true for n=1, this causes the equality to be true for all n.

Sorry im just abit confused on why you put $k^3$ on the left hand side to make it all equal $(k+1)^3$ ?

**Archie Meade** · April 19th 2010, 05:39 AM

Originally Posted by jvignacio

Sorry im just abit confused on why you put $k^3$ on the left hand side to make it all equal $(k+1)^3$ ?

The reason is...

if $1+7+19+....+\left(3k^2-3k+1\right)=k^3$

then the sum of the first k terms is $k^3$

This means that the sum of the first $(k+1)$ terms will be $(k+1)^3$

if this equality really is true!

Think about that.

However, the sum of the first $(k+1)$ terms is the sum of the first k terms plus the (k+1)th term, which is

$k^3+(k+1)th\ term=k^3+\left[3(k+1)^2-3(k+1)+1\right]$

if the sum of the first k terms really is $k^3$

You get the (k+1)th term by using k+1 in place of k.

Then you need to show that when you add the sum of k terms (which is supposed to be $k^3$ ) to the (k+1)th term,

the answer should be $(k+1)^3$

If this is the case, then we can say

$sum\ of\ terms=k^3$ causes the $sum\ of\ k+1\ terms$ to be $(k+1)^3$

All we've done is to show that the formula being true for a particular value of n=k
will cause the formula to be true for the next value of n=k+1.

That establishes a chain reaction.
Then if you test it for n=1, and it's true, then it's true for all natural numbers n.

Since this may seem long-winded, it's generally not covered in class.

There are shortcut ways to prove the initial statement,
such as

test for n=1
assume p(k) true.....test p(k+1)

but it's easier if you understand the process.

Thread: induction help

LinkBack

Thread Tools

Display

induction help

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Induction

Rigorously prove the principle of complete induction from mathematical induction??

Mathemtical Induction Proof (Stuck on induction)

induction

Search Tags