Mathematical Induction proof

Question

How to prove by mathematical Induction?

Answer 1

In general, inductive proofs follow these steps:

1. Show the equation is true for a base case (often n=0, n=1, or some small "starter" value)
2. Assume the equation is true for n = k
3. Show that from the assumption, one can infer the equation is true for n = k+1

_n

S_n = ∑ (5j - 1)

^j=1

Let n = 1: S₁ = 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 S_n = (k/2)(3+5k) for n = k. This is our assumption (the hypothesis)

Let n = k+1:

_{n=k+1 n=k}

S_k+1 = ∑ (5j - 1) = ∑ (5j - 1) + (5(k+1) - 1)

^{j=1 j=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 :

S_k+1 = (k/2)(3+5k) + (5k+4) = (1/2) (3k + 5k² + 10k + 8) = (1/2)(5k² + 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 + 5k² + 5(2k) + 5(1))

= (1/2)(5k² + 13k + 8)

Same as RHS of (1), so proof is complete.