In general, inductive proofs follow these steps:
- Show the equation is true for a base case (often n=0, n=1, or some small "starter" value)
- Assume the equation is true for n = k
- Show that from the assumption, one can infer the equation is true for n = k+1
Sn = ∑ (5j - 1)
Let n = 1: S1 = 5(1) - 1 = 4 and (1/2)(3 + 5(1)) = (1/2)(8) = 4 So the pattern is true for n=1. That's the base case.
Assume Sn = (k/2)(3+5k) for n = k. This is our assumption (the hypothesis)
Let n = k+1:
Sk+1 = ∑ (5j - 1) = ∑ (5j - 1) + (5(k+1) - 1)
The last two terms are just the n=k portion (under the summation sign) and final ( k+1 )th term separated out. The n=k portion, by hypothesis, is equal to (k/2)(3+5k). Replacing the n=k portion and simplifying 5(k+1)-1 = 5k+4 :
Sk+1 = (k/2)(3+5k) + (5k+4) = (1/2) (3k + 5k2 + 10k + 8) = (1/2)(5k2 + 13k + 8) (1)
I assert this is equal to ((k+1)/2) (3 + 5(k+1)) which would be the end of the proof (i.e. assuming truth for n=k leads to truth for n=k+1). But I still need to show equality...
Let's just compute ((k+1)/2) (3 + 5(k+1)) it to see if we can get the same expression as the RHS of (1):
((k+1)/2)(3 + 5(k+1))
= (1/2)(3(k+1) + 5(k+1)(k+1))
= (1/2)(3k+ 3 + 5k2 + 5(2k) + 5(1))
= (1/2)(5k2 + 13k + 8)
Same as RHS of (1), so proof is complete.