1. ## Mathematics induction concepts

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

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

Therefore, you assume that

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

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

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

So:

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

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

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

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

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

Q.E.D.

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

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

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

6. 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)

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

P(k+1)

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

Proof

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

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

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

7. 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..... $\displaystyle k^2\ge\ 2k$

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

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

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

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