# CMPUT272 Lecture Notes - Lecture 10: Natural Number, Chessboard

October 2 2014

ETLC 2-001

Theroem: for all n +, 1^2 + 2^2 + ... + n^2 = (1/6)n(n+1)(2n+1)∈ ℤ

n

1^2 + 2^2 + ... + n^2 = ∑(i^2)

i=1

How to prove?

1

for n = 1: ∑ i^2 = 1^2 = 1 = (1/6)n(n+1)(2n+1) = (1/6)(1)(2)(3) = 1

i=1

Thus, the thereom holds for n = 1

2

for n = 2: ∑ i^2 = 1^2 + 2^2 = 5 = (1/6)n(n+1)(2n+1) = (1/6)(2)(3)(5) = 5

i=1

Thus, the tereom holds for n = 2

Suppose we have verified up to n = k

k

for n = k: ∑ i^2 = = (1/6)(k)(k+1)(2k+1)

i=1

How does the sum change as n increases from k, to k + 1?

k

∑ i^2 = 1^2 + 2^2 + .. + k^2

i=1

k+1

∑ i^2 = 1^2 + 2^2 + .. + k^2 + (k+1)^2

i=1

So, for n = k+1

k+1 k

∑ i^2 = ∑ i^2 + (k+1)^2

i=1 i=1

Which is equivilant to

= (1/6)(k)(k+1)(2k+1) + (k+1)^2

[[ Want: = (1/6)(k+1)(k+2)(2(k+1)+1) ]]

Thus, by substituting the equivilance back to the summation..

(Use the result from previous case to prove next case)

k+1

∑ i^2 = (1/6)(k)(k+1)(2k+1) + (k+1)^2

i=1

= (k+1)((1/6)(k)(2k+1) + (k+1))

= (1/6)(k+1)(k(2k+1) + 6(k+1))

= (1/6)(k+1)(k+2)(2k+3)

= (1/6)(k+1)((k+1)+1)(2(k+1)+1)

Yaya!

So, the thereom is true for n = k + 1

Now we can verify k+2, k+3, ...

the thereom is true.∴

What have we proved?

Let P(n) be the predicate on domain +ℤ

n

∑ i^2 = (1/6)(n)(n+1)(2n12)

i=1

We proved P(a), P(a+1), P(a+2)... k ,k≥a, (P(k) P(k+1))∀ ∈ℤ ⟹

P(1) P(2) P(3) P(4) ....⟹ ⟹ ⟹ ⟹

\----------/

P(2) (Modus Pones)

\--------------/

P(3) (Modes Pones)

...

Using..

1. Hypothetical reasoning

2. Universal generaliztion

Principal of Mathamatical Induction

Let P(n) be defined on domain . Let a ℤ ∈ ℤ

If

1. P(a) is true, and.

2. for all k ,k≥a, (if P(k) is true then P(k+1) is true)∈ ℤ

Then

for all n ,k≥a, P(n) is true∈ ℤ

Method

0. Introduction

State how proof is shown (e.g. 'by induction')

Define approriate predicate

1. Base case (or basis step): Prove P(a)

## Document Summary

Theroem: for all n +, 1^2 + 2^2 + + n^2 = (1/6)n(n+1)(2n+1) n. 1^2 + 2^2 + + n^2 = (i^2) i=1. 1 for n = 1: i^2 = 1^2 = 1 = (1/6)n(n+1)(2n+1) = (1/6)(1)(2)(3) = 1 i=1. Thus, the thereom holds for n = 1. 2 for n = 2: i^2 = 1^2 + 2^2 = 5 = (1/6)n(n+1)(2n+1) = (1/6)(2)(3)(5) = 5 i=1. Thus, the tereom holds for n = 2. Suppose we have verified up to n = k k for n = k: i^2 = = (1/6)(k)(k+1)(2k+1) i=1. How does the sum change as n increases from k, to k + 1? k. I^2 = 1^2 + 2^2 + + k^2 i=1 k+1. I^2 = 1^2 + 2^2 + + k^2 + (k+1)^2 i=1. Thus, by substituting the equivilance back to the summation (use the result from previous case to prove next case) k+1.