CMPUT272 Lecture Notes - Lecture 10: Natural Number, Chessboard

47 views5 pages
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) ]]
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in
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)
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in

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.

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers