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
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
They claim in particular that k^2 + 2k + 1 >= 2k + 2k + 1. This follows from the induction hypothesis that says k^2 >= 2k.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.
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)
P(k+1)
hopefully!
Proof
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.
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.