1
$\begingroup$

This might be a silly question but I have never had proofs at school and I get stuck at the uni especially in a foreign country. So here goes...

The following needs to be proven by Mathematical Induction:

enter image description here

This is an example in my Script so here is the solution as well:

Step 1: (I will skip this, it's just n=1 and it is correct)

Step 2: $A(n) \implies A(n+1)$

enter image description here

Well, I understand what is written there, but, when I 'follow the instructions' of the Mathematical Proof I get something like this (I basically put $n+1$ instead of $n$):

$$\sum_{k=1}^{n+1} k = \frac {(n+1)*(n+2)}{2} = (n+1) + \sum_{k=1}^{n} k = \frac {(n+1)*(n+2)}{2}$$

$$\sum_{k=1}^{n} k = \frac {(n+1)*(n+2)}{2} - (n+1) =\frac {n*(n+1)}{2} $$

Is what am I doing also proof and equivalent to the other solution given above, or am I completely lost?

Thanks!

$\endgroup$
1
  • $\begingroup$ You do need to go the right way to use induction. However, using reversible steps to work backwards can, in some cases, show how the induction can be carried through. $\endgroup$ Feb 11 '17 at 19:56
1
$\begingroup$

Assuming $$\sum_{k=1}^nk=\frac{n(n+1)}{2}$$ you should check that $$\sum_{k=1}^{n+1}k=\frac{(n+1)(n+2)}{2},$$ but you start from this equation. You must not assume the assertion of the theorem.

The proof given in a picture you show us goes exactly in this direction.

$\endgroup$
2
  • $\begingroup$ so basically, I am going backwards, or something like that yea? $\endgroup$
    – Leonardo
    Feb 11 '17 at 19:49
  • $\begingroup$ What you are calling "going backwords" is the induction hypothesis. In the case in question this is the equation $$\sum_{k=1}^nk=\frac{n(n+1)}{2}.$$ Of course, there are also more advanced techniques of induction proofs, but this which we discuss is the most typical one. $\endgroup$
    – szw1710
    Feb 11 '17 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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