Discete Math Discete Math Prove 3 11 middot middot middot

Discete Math:

Discete Math: Prove 3 + 11 + middot middot middot + (8_n - 5) = 4n^2 - n for n P.

Solution

The LHS (left-hand side) of the statement P(1) is 3 + 11 + · · · + (8(1) 5) = 3. The RHS (right-hand side) of P(1) is 4(1)^2 1 = 4 1 = 3. Since these are equal this shows that P(1) is true. This completes the proof of the basis step.

Inductive Step: Let k be a positive integer and and assume that P(k) is true. This means that

3 + 11 + 19 + · · · + (8k 5) = 4k ^2 k. The LHS of P(k + 1) is 3 + 11 + 19 + · · · + (8(k + 1) 5) = 3 + 11 + 19 + · · · + 8k + (8(k + 1) 5), and since P(k) is true we can write this as 4k ^2 k + (8(k + 1) 5) = 4k^ 2 + 7k + 3. The RHS of P(k + 1) is 4(k + 1)2 (k + 1) = 4(k 2 + 2k + 1) k 1 = 4k 2 + 7k + 3. Therefore P(k + 1) is true since its left and right hand sides are equal. This shows (by a direct proof) that P(k) implies P(k + 1), and completes the proof of the inductive step. We conclude that P(n) is true for every positive integer n by the Principle of Mathematical Induction.