1. ## Mathematical Induction

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 = $\displaystyle 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)

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

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

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

3. Originally Posted by dunsta
$\displaystyle \frac{k(k+1)}{2} + (k+1)$

=
$\displaystyle \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..

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

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

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

oh I get it now, working backwards I see that
$\displaystyle \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 $\displaystyle 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?

5. 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.

6. One last question on this topic, if I may.

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

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

7. Originally Posted by dunsta
One last question on this topic, if I may.

Is it common knowledge in maths to simplify
$\displaystyle {k^2+3k+2}$
to
$\displaystyle {(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)

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

P(k+1)

substitute k+1 for k

$\displaystyle 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 $\displaystyle \frac{(k+1)(k+2)}{2}$

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

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