Induction: Truth Beyond Finiteness PDF

Induction Truth Beyond Finiteness Prof. Dr. Deniz Karlı Department of Mathematics IŞIK UNIVERSITY Version #: 28–11–2023 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 2 In our previous discussions: Modern Mathematics was born after Axiomatic Foundations were established. What ar...

Induction Truth Beyond Finiteness Prof. Dr. Deniz Karlı Department of Mathematics IŞIK UNIVERSITY Version #: 28–11–2023 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 2 In our previous discussions: Modern Mathematics was born after Axiomatic Foundations were established. What are characteristic properties after this achievement: For a theory in Mathematics, assumptions (axioms) must be properly defined. All terminology must be clearly defined. Every statement (theorem) proposed (or deducted from other statements) must be made ”universally valid”. Every statement has to be ”consistent” with the rest of the theory. IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 3 Modern Mathematics is about ”Consistency” and ”Universal Validity”. How does Mathematics manage to be ”Universally Valid”? IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Universal Validity Clearly stated axioms and definitions Proofs 4 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Part I: Mathematical Proofs 5 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Is the truth just what we see? What if there exists more beyond what we can observe? 6 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 7 What is a Mathematical Proof? For a statement to be universally valid, it should be paired with a ”convincing argument”. A proof is a set of statements which uses axioms and previously validated theorems to show validity of a claimed argument. ”Proofs are stories that convince suitably qualified others that a certain statement is true.” by Keith Devlin IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 8 How does a Mathematical Proof work? A proof begins with assumptions of the statement (theorem). Following rules of logic, one deduce a chain of arguments. Every piece of this chain is properly discussed and validated by mathematical tools from previous pieces of the chain. The chain of argument continues until obtaining the conclusion which was claimed in the main statement (theorem). Claim & Assumptions of the Statement Conclusion proved from Statement n Statement 1 proved from claim Statement 2 proved from Statement 1 Statement n proved from Statement n−1 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Why Numerical Observations are not Enough? Why shouldn’t we convinced just by our observations? Let us consider the following inequality. This is a claim. Is this claim correct? n7 > 2n − 3. Here are some values (numerical observations): n n7 1 5 10 20 30 1 78, 125 10, 000, 000 1, 280, 000, 000 21, 870, 000, 000 It looks like the claim works (?) 2n − 3 > > > > > −1 29 1, 021 1, 048, 573 1, 073, 741, 821 9 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı ??? 10 n7 > 2n − 3 ??? But wait !!!!! n n7 2n − 3 40 163, 840, 000, 000 1, 099, 511, 627, 773 Conclusion: Numeric observations can be made only up to some finite value. No matter how large this value gets, a claim may be falsified afterwards. Hence numerical observations are NOT proofs. IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı So, how can we be sure of ”the truth”? 11 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 12 Part II: Gauss Sum & Sum of Powers Consecutive Numbers & Visual Illustrations IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 13 Sum of Consecutive Numbers In the 1780s, in a primary school in Germany, a teacher gave his class the tedious assignment of summing the first 100 integers. 1 + 2 + 3 +... + 98 + 99 + 100 The teacher’s aim was to keep the kids quiet for half an hour. But one young pupil almost immediately produced an answer: 1 + 2 + 3 +... + 98 + 99 + 100 = 5, 050. IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 14 The teacher couldn’t understand how his pupil had calculated the sum so quickly in his head. He was just eight years old. Do you recognize this genius? IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 15 Gauss’ Sum The teacher couldn’t understand how his pupil had calculated the sum so quickly in his head. He was just eight years old. Yes, This genius was Carl Friedrich Gauss, who would be later recognized as being one of the greatest mathematicians of all time. But how did he solve the problem so quickly? IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 16 Gauss’ idea to find the sum was quite clear, simple and smart. He wrote the sequence of these numbers forward and backwards once. Do you see any pattern below? 1 100 ↓ 101 A + + 2 99 ↓ 101 + + 3 98 ↓ + +......... + + 101 togethe 98 3 ↓ + + 101 2 G 6 10 99 2 ↓ 101 + + 100 1 ↓ 101 ro 1002L 502 6 100.101 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 17 Generalized Gauss’ Sum Clearly, this idea may be generalized to the sum up to any positive integer n. O 1 n ↓ + + n 1 Twice the 1 2 3 0 2 n−1 ↓ 3 0 n−2 + + + + ↓......... n sum n n−2 3 ↓ 0 Cuts att 1 + + net nezle + + n−1 2 ↓ 0 n 1 + + n 1 ↓ 0 net Gazsem 2 3 50 51 1 EE 2 4 Ee 1 1 30 3 6 2 3 5251 50 80 8 100 99 5 33 neyle tn 36 39 150 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 18 Generalized Gauss’ Sum Note that we state a pretty convincing idea to show validity of this argument. No matter which language a person is talking or from which culture the person is, he/she will be convinced (by providing some details) in the truthiness of this argument. This is the key idea behind a proof. There are various ways of proofs. For example, we can prove the validity of Gauss’ Sum by a visual proof: Consider area of this shape in terms of number of squares IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 19 Visual Proof of Gauss’ Sum ① ③ ② Thar ④ e contain this rectangle But each square twice So the initial blue ones ofsquares YE IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Are there other formulas which can be shown like this way? 20 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 21 Sum of Squares How about sum of squares of positive integers up to n? 12 + 22 32 + +... + (n − 2)2 + (n − 1)2 42 + 52 =? For example, if n = 5, 12 + 22 + 32 + + n2 =? IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sum of Squares 12 + 22 Tent + 32 + 42 + 52 =? like 22 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sum of Squares 12 + p 22 23 u IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sum of Squares 12 + 22 + 32 0 24 u IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sum of Squares 12 + 22 + 32 + 42 25 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 26 Sum of Squares 12 + 22 + 32 + 42 52 + sum of all squares Eiko 554k 5 5 5 4 4 941 1 7 5 52 bg 3 2 2 I 112 3 4 5 5 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 27 Sum of Squares In General 12 n + 22 + 32 +... + (n − 2)2 + (n − 1)2 + xn ncntfkn.ae iH n2 =? In 1 2 nl Sum E E of squares 12 22 104114 1427 20 tn LE2nt1 20.21.41 252 4 ü IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 28 Sum of Cubes How about sum of cubes of positive integers up to sum n? 13 + 23 33 + +... + (n − 2)3 + (n − 1)3 43 + 53 =? For example, if n = 5, 13 + 23 + 33 + + n3 =? IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 13 + 23 + 33 + 43 + 53 =? 521 EEE 5 5 3 5 29 Sum of cubes 13 23 33 13 27 E 1 m 103 1 203 103 113 2 1 552 1 13 24 1 203 14 203 53 52 63 62 73 72 103 10 113 11 en 303 30 9 20 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 30 Sigma Notation There is a mathematical notation which simplifies all these summation representations. ! −notation Here Σ means that we add values with respect to consecutive indices. In other words: n ! k=1 ak = a1 + a2 + a3 + · · · + an−1 + an IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sigma Notation - Examples 5 ! k=1+2+3+4+5 k=1 7 ! k2 = 3 2 + 4 2 + 5 2 + 6 2 + 7 2 k=3 8 ! k=2 k3 = 2 3 + 3 3 + 4 3 + 5 3 + 6 3 + 7 3 + 8 3 31 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Sum of Integers, Squares & Cubes Using Sigma Notation What we showed by illustrations so far are as follows: n ! k=1 n ! k=1 k = 1 + 2 + 3 + ··· + n = k2 = 12 + 22 + 32 + · · · + n2 = n ! k=1 n(n + 1) 2 n(n + 1)(2n + 1) 6 k3 = 13 + 23 + 33 + · · · + n3 = " n(n + 1) 2 #2 32 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı These visual proofs are valid. However, they are very limited in application. Hence, they are not applicable in most of mathematical statements. 33 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Then, how can one prove a statement without the help of visual aids? 34 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Part III: Proof By Induction 35 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Proof By Induction How can we prove a statement based on integers such as 1,2,3,...? For example, for n = 2, we have 1+2= 2·3 2 for n = 3, we have 1+2+3= 3·4 2 for n = 4, we have 1+2+3+4= 4·5 2 Will this statement be ”true for sure” for n = 10, 000, 000? 36 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı How would you teach a kid to climb on a ladder? 1. Describe what to do with the first step of the ladder. 2. If the kid is on a step already, describe how to climb to the next step. 37 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı How would you describe the event of ”dominoes falling”? 1. Describe what happens to the first domino piece: ”Someone kicks the first piece”. 2. Describe what happens to a domino piece if the previous piece fall down. 38 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 39 Proof By Induction A proof by induction is a chain of arguments where each argument is evoked and proved by the previous argument. Base Statement P(1) P(2) ··· This chain has a ”first statement”. It is called the base statement. (P(1)) Then there is inductive step where one shows ”as long as one step is true, next step is always true”. (P(n) implies P(n + 1)) ··· P(n + 1) P(n) IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı For example, in proving Gauss’ sum using induction for n = 1, we have 1= For n = 2, we have 1·2. 2 1+2= For n = 3, we have This is the base statement P(1). 2·3. 2 1+2+3= And it goes so on. For a general n, we have 3·4. 2 This is the statement P(2). This is the statement P(3). n · (n + 1) 1 + 2 + 3 + ··· + n =. 2 This is the statement P(n). 40 IŞIK UNIVERSITY Base Statement P(1) : 1·2 1= 2 ”Induction: Truth Beyond Finiteness” by Deniz Karlı Statement P(2) : 1+2= 2·3 2 Statement P(n + 1) : ··· 1+· · ·+(n+1) = (n + 1) · (n + 2) 2 41 Statement P(3) : 1+2+3 = ··· 3·4 2 Statement P(n) : 1 + ··· + n = n · (n + 1) 2 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 42 Algorithm of Induction Prove the ”Base Statement” P(1) Prove the ”Inductive Step” P(n) =⇒ P(n + 1) for any n (which means ”if P(n) is true then so is P(n + 1)”.) Note that if one prove both ”Base Statement” and ”Inductive Step” then we have, P(1) is true; Since P(1) is true, then P(2) is true by definition of algorithm. Since P(2) is true, then P(3) is true by definition of algorithm. Since P(3) is true, then P(4) is true by definition of algorithm. And so similarly P(5), P(6),... are all true. Even P(10, 000, 000)! IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 43 Proof of Gauss’ Sum by Induction Claim: The claim is P(n) : n ! k=1 k = 1 + ··· + n = n · (n + 1) 2 Step 1: Prove the ”Base Step”. That is, prove the statement is true when n = 1. P(1) : 1= 1 · (1 + 1) 2 This equality is clearly true. Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. P(n) =⇒ P(n + 1) IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 44 Proof of Gauss’ Sum by Induction Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. Assume P(n) : 1 + ··· + n = n · (n + 1) 2 is true. (∗) Can we obtain P(n + 1) : (n + 1) · (n + 2) 1 + · · · + n + (n + 1) = 2 form (∗) above? If we can then we have a proof. IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 45 Proof of Gauss’ Sum by Induction Step 2: Let us try to show P(n + 1) 1 + 2 + 3 + · · · + n + (n + 1) = nfl 4 1 Cnn " # 1 + 2 + 3 + · · · + n + (n + 1) nfl HAINI 2 Intel E E IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 46 Proof of Sum of Squares by Induction Claim: The claim is P(n) : n ! k=1 k2 = 12 + · · · + n2 = n · (n + 1) · (2n + 1) 6 Step 1: Prove the ”Base Step”. That is, prove the statement is true when n = 1. P(1) : 12 = 1 · (1 + 1) · (2 + 1) 6 This equality is clearly true. Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. P(n) =⇒ P(n + 1) IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 47 Proof of Sum of Squares by Induction Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. Assume P(n) : 12 + · · · + n2 = n · (n + 1) · (2n + 1) 6 is true. (∗) Can we obtain P(n + 1) : (n + 1) · (n + 2) · (2(n + 1) + 1) 1 + · · · + n + (n + 1) = 6 2 2 2 form (∗) above? If we can then we have a proof. IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 48 Proof of Sum of Squares by Induction Step 2: Let us try to show P(n + 1) 12 + 22 + 32 + · · · + n2 + (n + 1)2 = ninjas 4 1 4176 71 hala 6411 62 " 12 + 22 + 32 + · · · + n2 Intel 4 1 # + (n + 1)2 aklan E6 Cnn Intake IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 49 Proof of Sum of Cubes by Induction Claim: The claim is n ! P(n) : k=1 k3 = 13 + · · · + n3 = " n · (n + 1) 2 #2 Step 1: Prove the ”Base Step”. That is, prove the statement is true when n = 1. P(1) : 13 = " 1 · (1 + 1) 2 #2 This equality is clearly true. Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. P(n) =⇒ P(n + 1) IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 50 Proof of Sum of Cubes by Induction Step 2: Prove the ”Inductive Step”. That is, prove the statement P(n + 1) is true if we assume P(n) is true. Assume P(n) : 13 + · · · + n3 = " n · (n + 1) 2 #2 is true. (∗) Can we obtain P(n + 1) : 13 + · · · + n3 + (n + 1)3 = form (∗) above? If we can then we have a proof. " (n + 1) · (n + 2) 2 #2 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı 51 Proof of Sum of Cubes by Induction Step 2: Let us try to show P(n + 1) 13 + 23 + 33 + · · · + n3 + (n + 1)3 = IYI 4 15 Inte n 1 " 13 + 23 + 33 + · · · + n3 n 1 # + (n + 1)3 4 112 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı Exercise Problems to Use Induction 1. 2. 3. 4. n ! k=1 n ! k=1 n ! k=1 n ! k=1 " 1 n = k · (k + 1) n+1 ta (−1)n · n · (n + 1) (−1) · k = 2 k 2 (2k − 1) = n2 (Sum of first n positive odd integers) (2k) = n(n + 1) (Sum of first n positive even integers) # " # " # " # 1 1 1 1 n+1 5. 1 − 2 · 1 − 2 · 1 − 2 · · · · · 1 − 2 = 2 3 4 n 2n n ! n · (3n − 1) 6. (3k − 2) = 2 k=1 52 IŞIK UNIVERSITY ”Induction: Truth Beyond Finiteness” by Deniz Karlı End of Lecture 53