Thread: Strong induction proofs

i'm having trouble understanding strong induction proofs
i understand how to do ordinary induction proofs and i understand that strong induction proofs are the same as ordinary with the exception that you have to assume that the theorem holds for all numbers up to and including some n (starting at the base case) then we try and show: theorem holds for n+1
but how do you show this exactly.
here is a proof by induction:

---

Thm: n≥1, 1+6+11+16+...+(5n-4) = [n(5n-3)]/2 Proof (by induction)
Basis step: for n=1: 5-4=(5-3)/2 ---> 1=1 the basis step holds
Induction Step: Suppose that for some integer k≥1 1+6+11+16+...+(5k-4) = [k(5k-3)]/2 (inductive hypothesis)
Want to Show: 1+6+11+16+...+(5k-4)+(5{k+1}-4) = [{k+1}(5{k+1}-3)]/2
[k(5k-3)]/2 + (5{k+1}-4) = [{k+1}(5{k+1}-3)]/2

---

then you just show that they are equal
so how can i do the same proof using strong induction? what are the things i need to add/change in order for this proof to be a strong induction proof?

Technically, every proof by regular induction is also a proof by strong induction because in strong induction, you are allowed to use the hypotheses for all numbers up to n; you are not required to use any of them. Of course, for clarity we usually describe only the necessary tools used in a particular proof, so a proof that uses only the induction hypothesis for n is properly described as using regular induction.

Usually either regular or strong induction is more convenient. Proving the formula for the sum of an arithmetic progression is more convenient using regular induction, and proving that every natural number > 1 can be factorized into primes is more convenient using strong induction. Sometimes it is possible to give both proofs. For example, suppose we want to prove 1 + ... + (5n - 4) = n(5n - 3) / 2 from the hypotheses for all k < n. If n = 2k, then k < n since n ≥ 1. The left-hand side equals

1 + ... + (5k - 4) + (5k + 1) + ... + (5(2k) - 4) =
1 + ... + (5k - 4) + 5k² + 1 + ... + (5k - 4) =
k(5k - 3) / 2 + 5k² + k(5k - 3) / 2 =
10k² - 3k

and the right-hand side also equals (2k)(5(2k) - 3) / 2 = 10k² - 3k. The case when n = 2k + 1 should be considered similarly. However, this proof seems more complicated.

For another example where both regular and strong inductions are appropriate see this thread.