# Induction help

• May 26th 2011, 12:55 PM
monkbear
Induction help
Hi I need help in regards with proving this problem.

If the sequence is 1,13,37,73,121
then it should follow like this 1+12+24+36......12n+(12n+12)
For the formula 6n^2 - 6n + 1.

How would I go on to prove this with induction exactly? Thanks
• May 26th 2011, 01:08 PM
Plato
Quote:

Originally Posted by monkbear
Hi I need help in regards with proving this problem.
If the sequence is 1,13,37,73,121
then it should follow like this 1+12+24+36......12n+(12n+12)
For the formula 6n^2 - 6n + 1.
How would I go on to prove this with induction exactly? Thanks

• May 26th 2011, 02:08 PM
bryangoodrich
Quote:

Originally Posted by monkbear
How would I go on to prove this with induction exactly? Thanks

Induction works in two steps. First you prove it true for some base case. In this case, if P(n) reads

$1 + 12 + 24 + ... + 12n + (12n + 12) = 6n^2 - 6n + 1$

show that P(0) is true. That should be straight-forward computation. The inductive step is to assume it is true for some $k \geq 0$. Assuming P(k), demonstrate P(k+1). By establishing those two facts regarding P(n), you can prove it is true for every $n\geq 0$. Do you understand why this two-step process works? In other words, do you know why the principle of mathematical induction (PMI) is a valid rule of inference?

Quote:

Originally Posted by Plato

That link didn't work for me Plato (using FF2). Broken?
• May 26th 2011, 02:18 PM
Plato
Quote:

Originally Posted by bryangoodrich
that link didn't work for me plato (using ff2). Broken?

fixed.
• May 26th 2011, 03:14 PM
bryangoodrich
I've never used Wolfram Alpha before, but I have to say ... that's awesome!
• May 27th 2011, 04:20 AM
Quote:

Originally Posted by monkbear
Hi I need help in regards with proving this problem.

If the sequence is 1,13,37,73,121
then it should follow like this 1+12+24+36......12n+(12n+12)
For the formula 6n^2 - 6n + 1.

How would I go on to prove this with induction exactly? Thanks

You should have a closer look at the pattern.

$u_1=1=1+12(0)$

$u_2=13=1+12(1)$

$u_3=37=1+12(1)+12(2)$

$u_n=1+12(1)+12(2)+....+12(n-1)$

To prove using induction that

$u_n=1+12(1)+12(2)+....+12(n-1)=6n^2-6n+1$

P(k)

$1+12(1)+12(2)+....+12(k-1)=6k^2-6k+1$

P(k+1)

$1+12(1)+12(2)+.....+12(k-1)+12k=6(k+1)^2-6(k+1)+1\;\;\;?$

Try to show that IF P(k) is true THEN P(k+1) will also be true.

Proof

If P(k) is true, then P(k+1) is

$1+12(1)+12(2)+...+12(k-1)+12k=6k^2-6k+1+12k=6k^2+6k+1$

which compares to

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

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

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

It remains to test the base case for n = 1, which is clearly true.