Thread: Math Induction Confusing

Im reading this: Tutorial: Mathematical Induction

Now it says at the end: "The formula works for k+1, and this is what we needed to show."
But how does (k^2+2k+1)/2 show it works for k+1??

What he is writing looks pretty much like nonsense to me!

At one point he has $\displaystyle k= \frac{k(k+1)}{2}$ which is certainly NOT true for all k.


It may be just bad formatting- perhaps a sum is not showing up.

In order to prove $\displaystyle 1+ 2+ 3+ \cdot\cdot\cdot+ n= \frac{n(n+1)}{2}$ by induction, you first prove it is true for n= 1: on the left we just have 1 and on the right [tex]\frac{1(1+1)}{2}= 1. Those are the same so the formula is true for n= 1. That is what he shows and that is correct.

Next we assume the formula is correct for some value k. (Notice that we are NOT assuming the formula is correct for all numbers- that is what we want to prove.)

That is, [tex]1+ 2+ 3+ \cdot\cdot\cdot+ k= \frac{k(k+1)}{2}[\math]
Notice the sum on the left that is missing from what he says.

Now, what about $\displaystyle 1+ 2+ \cdot\cdot\cdot+ k+ (k+1)$? We can replace the first part of that, the $\displaystyle 1+ 2+ \cdot\cdot\cdot + k$ with the formula above:
$\displaystyle 1+ 2+ \cdot\cdot\cdot+ k+ (k+1)= \frac{k(k+1)}{2}+ k+ 1$

That is the same as $\displaystyle \frac{k(k+1)}{2}+ \frac{2(k+1)}{2}$

We can factor "k+1" out of that:
$\displaystyle (k+1)\frac{k}{2}+ \frac{2}{2}= \frac{(k+1)(k+2)}{2}$
which is just
$\displaystyle \frac{(k+1)((k+1)+1)}{2}$
Our original formula with n replaced by k+1.

That is if the formula is correct for n= k then it is correct for n= k+1.

We know it is correct for n= 1 so it is correct for n= 1+ 1= 2.

And since it is correct for n= 2, it is correct for n= 2+ 1= 3, and so on.

Either there is some really unfortunate formatting on that sight that is preventing things from showing up or the guy who wrote it really has no clue about induction.