0
$\begingroup$

I'm learning about proofs using induction and our professor want us to always use strong induction when giving proofs. In my understanding, strong induction is used to show the range of numbers you have shown to be true. I want to be able to write a complete and clear proof. I'm not really understanding how to correctly write the inductive hypothesis for this problem: for all natural numbers n, prove 1+2+3,+...+ n = n(n+1)/2.

I already showed the base case is true when n = 1. But for the inductive step I want to know if I did it right or not. Even if its correct, is there anything I can add or remove to make it clearer? This is what I have so far:

Inductive hypothesis:
If n <= k and n >= 1, assume 1+2+3+...+k = k(k+1)/2 is true for 1 <= n <= k.
Prove 1+2+3+...+ k+(k+1) = (k+1)(k+1+1)/2.

I know how to show the proof after this, I just want to understand how to write the inductive hypothesis. Thanks for any help.

$\endgroup$
0
$\begingroup$

The big difference between what is called strong induction and weak induction is the following.

In strong induction, you get to assume the inductive hypothesis is true for all integers up to and including $k$. You use this to prove the statement works for the next one, $k+1$.

In weak induction, you only assume the inductive hypothesis for $k$. You then use this to prove $k+1$.

These two methods are logically equivalent of course though. This example is maybe not the best to see the power of strong induction though, because you really only need the $k$ result to prove the $k+1$ result is true. You can imagine some scenario's where you might need to use the result for integers smaller than just the previous one.

This site has some nice problems using induction. Question 10 catches my eye as a standard use of strong induction. http://www.math.uiuc.edu/~hildebr/213/inductionsampler.pdf

$\endgroup$

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.