induction help

• Apr 19th 2010, 02:42 AM
jvignacio
induction help
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.
• Apr 19th 2010, 03:53 AM
BabyMilo
Sorry this is wrong. O.o
• Apr 19th 2010, 04:04 AM
Quote:

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.
• Apr 19th 2010, 04:11 AM
jvignacio
Quote:

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$ ?
• Apr 19th 2010, 04:17 AM
jvignacio
Quote:

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$
• Apr 19th 2010, 04:25 AM
Quote:

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
• Apr 19th 2010, 06:13 AM
jvignacio
Quote:

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$?
• Apr 19th 2010, 06:39 AM
Quote:

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!

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.