1. ## induction help

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

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

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

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

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

2. Sorry this is wrong. O.o

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

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

My answer: Is this just substituting $\displaystyle n=1$ into $\displaystyle 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 + .... + ($\displaystyle 3k^2 - 3k + 1$) = $\displaystyle k^3$, then 1 + 3 + 5 + ... + ($\displaystyle 3k^2 - 3k + 1$) + $\displaystyle (3(k + 1)^2 -3(k + 1) +1$) = $\displaystyle (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.

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

If it is then examining

$\displaystyle 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 $\displaystyle (k+1)^3$ if the sum of k terms is $\displaystyle k^3,$ we get

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

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

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

$\displaystyle (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$$\displaystyle =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. 4. Originally Posted by BabyMilo \displaystyle 3n^2-3n+1 does not = \displaystyle 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=\displaystyle k^3+k+1, while RHS=\displaystyle k^3+3k^2+3k+1 Hope this helps! for a) shouldnt it be \displaystyle LHS = 1, \displaystyle RHS = n^3 = 1^3 = 1, therefore true for \displaystyle n=1 ? 5. 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. \displaystyle 1+7+19+...+(3k^2-3k+1)=k^3 ? If it is then examining \displaystyle 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 \displaystyle (k+1)^3 if the sum of k terms is \displaystyle k^3, we get \displaystyle k^3+3(k+1)^2-3(k+1)+1=k^3+3(k^2+2k+1)-3(k+1)+1 \displaystyle =k^3+3k^2+6k+3-3k-3+1=k^3+3k^2+3k+1 which is \displaystyle (k+1)^3, since \displaystyle (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$$\displaystyle =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 $\displaystyle n^3$ OR $\displaystyle 3n^2 - 3n + 1$

6. Originally Posted by jvignacio
For a) do I substitute n=1 into $\displaystyle n^3$ OR $\displaystyle 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 $\displaystyle 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).

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

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

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

The $\displaystyle n^3$ is the sum of these

$\displaystyle 1=1^3$

$\displaystyle 1+7=2^3$

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

7. Originally Posted by Archie Meade
and examining if this is $\displaystyle (k+1)^3$ if the sum of k terms is $\displaystyle k^3,$ we get

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

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

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

$\displaystyle (k+1)^3=(k+1)^2(k+1)=\left(k^2+2k+1\right)(k+1)$$\displaystyle =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 $\displaystyle k^3$ on the left hand side to make it all equal $\displaystyle (k+1)^3$?

8. Originally Posted by jvignacio
Sorry im just abit confused on why you put $\displaystyle k^3$ on the left hand side to make it all equal $\displaystyle (k+1)^3$?
The reason is...

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

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

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

if this equality really is true!

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

$\displaystyle 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 $\displaystyle 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 $\displaystyle k^3$) to the (k+1)th term,

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

If this is the case, then we can say

$\displaystyle sum\ of\ terms=k^3$ causes the $\displaystyle sum\ of\ k+1\ terms$ to be $\displaystyle (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.