Mathematical Induction

**dunsta** · June 7th 2010, 09:43 PM

Hi, I understand the sequence of the example I am working through, but I cannot understand some of the "simplification" (i.e. when one expression is simplified to mean the same thing)

The example is

Prove inductively for all integers n >= 1,
1+2+3....+n = $n(n+1) / 2$ ---> *

i) i understand s(subscript m ??) is true, I prove this by substituting an integer for n

ii) sn+1 is true when n>=m and sn are true

To prove for Sk+1 is true for n = k+1;
original k(k+1)/2 becomes
k(k+1)/2 + (k+1) ---I understand this is proof for n=k+1 where n is the formula above, marked ---> *

but I do not understand the next step in the example, where
(a) k(k+1)/2 + (k+1) <---this formula is simplified to:
= (b) (k+1)(k+2) / 2 <--- I don't understand how they went from (a) to (b) here.

I thought
k(k+1)/2 + (k+1) = k squared + k / 2 + (k+1) (sorry I can't get super/sub script to work)

Thanks for any help, sorry if my explanation seems jumbled or unreadable(if so I will try to post the example again more clearly)

**dunsta** · June 7th 2010, 10:06 PM

$ \frac{k(k+1)}{2} + (k+1) $

=
$ \frac{(k+1)(k+2)}{2} $

this is the equation, I don't understand how they got from a to b

**Drexel28** · June 7th 2010, 10:28 PM

Originally Posted by dunsta

$ \frac{k(k+1)}{2} + (k+1) $

=
$ \frac{(k+1)(k+2)}{2} $

this is the equation, I don't understand how they got from a to b

Don't forget high school algebra brah..

$\frac{k(k+1)}{2}+k+1=\frac{k(k+1)}{2}+\frac{2k+2}{ 2}=\frac{k^2+k+2k+2}{2}$ ..

**dunsta** · June 7th 2010, 11:15 PM

I didn't think I had forgotten that much algebra, but ...

$ \frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2} ... $

oh I get it now, working backwards I see that
$ \frac{(k+1)(k+2)}{2} = \frac{(k * k) + (k * 2) + (k * 1)+ (1 * 2)}{2}=\frac{k^2 + 2k + k + 2}{2} $

I just didnt associate (k+1)(k+2) with $k^2 + 2k + k + 2$
off the top of my head.

I will go back over my notes and hope I "get" the problem better next time through.

Thanks for the help.
BTW should I have posted this in the algebra formula?

**Drexel28** · June 8th 2010, 12:44 AM

Originally Posted by dunsta

Thanks for the help.
BTW should I have posted this in the algebra formula?

No problem!

Also, I don't think you would have needed to post this in the algebra forum. Because, despite this really being an algebra problem it is based on the premise of induction which usually goes in this forum.

**dunsta** · June 8th 2010, 01:06 AM

One last question on this topic, if I may.

Is it common knowledge in maths to simplify
${k^2+3k+2}$
to
${(k+1)(k+2)}$

as this seems to me to be another way to write the expression rather than a simplification?

**Archie Meade** · June 8th 2010, 02:41 AM

Originally Posted by dunsta

One last question on this topic, if I may.

Is it common knowledge in maths to simplify
${k^2+3k+2}$
to
${(k+1)(k+2)}$

as this seems to me to be another way to write the expression rather than a simplification?

Hi Dunsta, yes it's just alternative ways to write the same thing.

It's common in these induction problems because we try to establish an
infinite chain of cause and effect from the first term all the way through to infinity.

We try to discover that the formula being valid for n=1 causes it to be valid for n=2...
then valid for n=2 causes it to be valid for n=3...
valid for n=3 causes it to be valid for n=4...
valid for n=4 causes it to be valid for n=5....

all the way to infinity.

If we can prove that being valid for n=k causes it to be valid for n=k+1,
then we have proven all the foregoing in one step!!

Since this proves that any term k causes the formula to be valid for the next term k+1

So the induction step establishes whether or not this infinite chain exists.

In this case

P(k)

$1+2+3+.....+k=\frac{k(k+1)}{2}$

P(k+1)

substitute k+1 for k

$1+2+3+.....+k+(k+1)=\frac{(k+1)(k+2)}{2}$

We try to prove that P(k) being true causes P(k+1) to be true

Hence, we can either multiply out $\frac{(k+1)(k+2)}{2}$

and check that it's the same as $P(k)+(k+1)$ multiplied out

or factor $P(k)+(k+1)$ to see if it equals $\frac{(k+1)(k+2)}{2}$

Thread: Mathematical Induction

LinkBack

Thread Tools

Display