I'm reading a book(concrete Mathematics) and it uses a lot the concept of 'Math induction'. Thought I've been reading tutorials and examples about it, I'm still unable to understand it, the last 'basic' example I was reading is(my questions are the ones highlighted):

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

Then it indicates:

  • Step 1: Show is valid for n=1: $1=\frac{1(1+1)}{2}=\frac{2}{2}=1$
  • Step 2: Inductive step, assume is valid for n=k:

$1+2+...+k=\frac{k(k+1)}{2}$ //why do I need to substitute n by k? to me is exactly the same as doing nothing, I could work with n+1 instead

  • Step 3: Prove is valid for $n=k+1$, and the demo is:


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

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

= $\frac{(k+1)(k+2)}{2}$//How is getting this from the previous equation???????

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

Any help is appreciated, this 'basic thing' is driving me nuts.

  • $\begingroup$ I mean, I could answer most of these questions, but I don't honestly think they will really elucidate anything. I would check out a intro to induction on google to help you out $\endgroup$ Oct 9 '18 at 20:09
  • 3
    $\begingroup$ $k(k+1) + 2(k+1) = (k+2)(k+1)$ is just basic factorization. $\endgroup$ Oct 9 '18 at 20:10
  • $\begingroup$ @RushabhMehta As I mentioned, I've been through many examples (most of them showing exactly the same) and still don't get it $\endgroup$
    – Eduardo
    Oct 9 '18 at 20:21

The principle of induction is based in the Axioms of Peano, an Italian mathematician. It states that, if a set X is such that $1 \in X $ and every successor of X is also an element of X, that is: $s(X) \in X$, then this set is the set of natural numbers!

The idea is quite intuitive: if every successor of a number is in a set, and the set contains the first of numbers (1), then it must have its sucessor as an element (2), and the successor of successor (3) and so on.

Then what you do is that you actually don't substitute n for k. You test the validity of the expression for n=1. And then you check if the formula holds for a k+1 (successor), assuming it works for a given k.

So, you could actually work with $n$ and $n+1$. It's just a matter of mathematical rigour! :)

For your second question, how you get that from the equation, it's factorization.

  • 2
    $\begingroup$ I'm not sure the first paragraph is much help to the OP, nor do I think they care too much about rigour at this point that they're trying to get basic induction! $\endgroup$
    – YiFan
    Oct 9 '18 at 20:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.