Mathematics induction concepts

**taurus** · March 6th 2010, 10:26 PM

I need some help with mathematical induction, especially when related to Computer Science.
For example:
1+2+3..+n = n(n+1)/2

I have to proove for all n. Now the base case is n=1 so
1 = 1(1+1)/2 = 2/2 = 1

That part I get but now for any n+1 is where i get confused.
It is solved like this in a tutorial I read:
n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

And thats the apparent answer but how does that proove it? I dont get it.

Thanks
Phil

**Prove It** · March 6th 2010, 10:34 PM

Originally Posted by taurus

I need some help with mathematical induction, especially when related to Computer Science.
For example:
1+2+3..+n = n(n+1)/2

I have to proove for all n. Now the base case is n=1 so
1 = 1(1+1)/2 = 2/2 = 1

That part I get but now for any n+1 is where i get confused.
It is solved like this in a tutorial I read:
n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

And thats the apparent answer but how does that proove it? I dont get it.

Thanks
Phil

You are correct with the base step.

Now you need to assume that it is true for $n = k$ .

Therefore, you assume that

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

Using this assumption, you have to show that it is true for $n = k + 1$ . In other words, you have to show that

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

So:

$1 + 2 + 3 + \dots + k + (k + 1)$

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

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

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

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

Q.E.D.

**taurus** · March 6th 2010, 11:00 PM

Hmmm still confusing me, I dont get how that prooves n+1?

**taurus** · March 7th 2010, 12:12 AM

I was looking at this:
Mathematical Induction Tutorial
Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.

Thanks

**emakarov** · March 7th 2010, 10:01 AM

Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.

They claim in particular that k^2 + 2k + 1 >= 2k + 2k + 1. This follows from the induction hypothesis that says k^2 >= 2k.

**Archie Meade** · March 7th 2010, 10:23 AM

Originally Posted by taurus

I need some help with mathematical induction, especially when related to Computer Science.
For example:
1+2+3..+n = n(n+1)/2

I have to proove for all n. Now the base case is n=1 so
1 = 1(1+1)/2 = 2/2 = 1

That part I get but now for any n+1 is where i get confused.
It is solved like this in a tutorial I read:
n+1 = ((n+1)((n+1)+1))/2 = ((n^2)+2n+1)/2

And thats the apparent answer but how does that proove it? I dont get it.

Thanks
Phil

Hi Phil,

Proof By Induction attempts to establish an inter-term link.

It tries to set up a trail of gunpowder as follows...

The formula being valid for some term n causes it to be valid for the next term.

Because this is attempted for the general term, which is expressed as the formula,
what we are in fact doing is proving the following.....

Formula true for T1 causes it to be true for T2 causes it to be true for T3
causes it to be true for T4 causes it to be true..........causes it to be true in general.

You light the trail by testing the first term.
If it's true for the first term, the gunpowder catches fire.

In this case, we can prove if the formula is valid or not with the 2 steps mentioned.

P(k)

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

P(k+1)

$1+2+3+.......(n-1)+n=\frac{(n+1)}{2}(n+2)$ hopefully!

Proof

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

This is certainly true if P(k) is valid, no doubt about that.

The important step now is to express this in terms of P(k)

This is how we try to create that inter-term link.

$\frac{n}{2}(n+1)+(n+1)=(n+1)\left(\frac{n}{2}+1\ri ght)$

$=(n+1)\left(\frac{n}{2}+\frac{2}{2}\right)$

and from this we obtain the P(k+1) version.

This means that the formula being valid for some n
causes it to be true for the next n up, the next n after that, on and on....

Hence if it is valid for a beginning value of n, it's valid for all subsequent ones.

**Archie Meade** · March 7th 2010, 03:16 PM

Originally Posted by taurus

I was looking at this:
Mathematical Induction Tutorial
Scroll down to the bit saying: "But by the induction hypothesis, k^2 >= 2k, therefore...". Am confused at what is going on there? How did they get the "...>= 2k + 2k + 1..."? Would appreciate an explanation.

Thanks

Hi Phil,

there are other ways to word the situation...

What's really meant there is

"If..... $k^2\ge\ 2k$

Then... $k^2+(2k+1)\ge\ 2k+(2k+1)$

and since.... $k\ge\ 1\ \ \Rightarrow\ 2k\ge\ 1$

which means ... $(k+1)^2\ge\ 2(k+1)$

if.... $k^2\ge\ 2k$

This establishes the inter-term link.

Thread: Mathematics induction concepts

LinkBack

Thread Tools

Display

Mathematics induction concepts

Similar Math Help Forum Discussions

Explain the following concepts from course and how the concepts are related.

Confusing concepts

Prove my mathematics induction, trigonometry

Mathematics: Discrete-Mathematics (Algorithems)

Mathematics Of Degree (the New Mathematics !!!! )

Search Tags