Advanced Mathematics Proofs and Concepts

Year 9 Proof Dr J Frost (jfrost@tiffin.kingston.sch.uk) www.drfrostmaths.com Objectives: Understand what is meant by a proof, and examples of what does and what doesn t constitute a proof. Be able to solve problems involving oddness/evenness, consecutive numbers and involving digits. Last modified: 26th April 2016

How Many Examples Needed? In 1772 Euler noticed that the following equation gives prime numbers for many positive integers n: ?? ? + ?? We might wonder if the statement For all positive integers n, n2 n + 41 is prime is true. Try this for a few ?. How many examples of n would we need to show this statement is: a) True Infinitely Many One A Few b) False Infinitely Many One A Few The smallest value of ? for which this statement is false is: 41 ?

An Oxford entrance test question (yes, really!) Source: MAT B A C D The statement If ?, then ? is only falsified when ? is true but ? is false. If the condition of the statement is not true, then the statement is not applicable, and we can neither say it is true or false.

Counterexamples A counterexample is an example used to disprove a statement. Discussing in pairs, find counterexamples for the following statements: Statement Possible counterexample Prime numbers are always odd. 2 is prime, but not odd. ? 1 The square root of a number is always smaller than the number itself. 0.25 = 0.5, but 0.5 > 0.25. ? 2 If ? is prime then ? + 2 is prime. 2?2+ 11 is prime for all integer values of ? 7 is prime but 9 is not. ? 3 (2 112) + 11 will be divisible by 11 because 2 112 and 11 both are. ? 4

Types of Proofs Geometry Sequence Proofs The first two terms of a sequence are the numbers 1, 2. From then on, each term is obtained by adding 1 to the previous term and then dividing by the term before that. Prove that the sequence repeats. Prove that the exterior angle of a triangle is the sum of the two other interior angles. Consecutive Numbers Prove that the sum of any three consecutive integers is a multiple of 3. We already covered these in the Sequences II topic. Even/Odd e.g. Show that for all integers ?, ??+ ?is always even. Game Proofs If I have a perfect Connect 4 strategy for winning, how can I show it s perfect?

Even/Odd Proofs You will do this kind of proof at GCSE The key here is that all integers are either odd or even. We can therefore do a case analysis and consider these two different cases. Show that for any integer n, ?2+ ?is always even. 1. If n is odd: ??? ??? + ??? = ??? + ??? = ???? 2. If n is even: ???? ???? + ???? = ???? + ???? = ???? ? Therefore ?2+ ? is even for all integers.

Test Your Understanding Prove that ? ? 1 + 1 is odd for all integers ?. If ? is odd, ??? ???? + ??? = ??? If ? is even, ???? ??? + ??? = ??? Thus ? ? ? + ? is odd for all integers ?. A ? [IMC 2009 Q16] How many different positive integers ? are there for which ? and ?2+ 3 are both prime numbers? A 0 B 1 D 3 E infinitely many B C 2 (Hint: Think odd/even) Solution: B All prime numbers except 2 are odd. But ????+ ??? = ????, which can t be prime (and note ??+ ?can t be 2). This the only possibility is if ? = ?. ? Indeed ??+ ? = ? is prime. So there is one solution only.

Exercise 1 [SMC 2001 Q9] Which of the following numbers ? gives a counter-example for the statement: If ? is a prime number then ?2+ 2is also a prime number ? A 3 B 5 C 6 D 9 E none of them Solution: B ? 6 1 Prove that 2? + 1 is odd for all integers ?. If ? is odd, ???? ??? + ??? = ??? If ? is even, ???? ???? + ??? = ??? Therefore ?? + ? is odd for all integers ?. ? Prove that ?3 ? is always even for all integers ?. If ? is odd, ??? ??? ??? ??? = ???? If ? is even, ???? ???? ???? ???? = ???? Thus ?? ? is always even for all integers ?. ? 2 [SMC 2006 Q12] The factorial of ?, written ?! Is defined by ?! = 1 2 3 ?. Which of the following values of ? provides a counterexample to the statement: If ? is a prime number, then ?! + 1 is also a prime number ? A 1 B 2 C 3 D 4 E 5 Solution: E 7 3 Find the smallest positive counterexample for the statement If ? is prime, then ?2+ ? + 1is prime. Smallest is ? = ? as ??+ ? + ? = ?? = ?? ? ? 4 [Kangaroo Pink 2015 Q16] Which of the following values of ?is a counterexample to the statement, If ? is a prime number, then exactly one of ? 2 and ? + 2 is prime ? A 11 B 19 C 21 D 29 E 37 Solution: E ? ? 8 [SMC 2013 Q16] Andrew states that every composite number of the form 8? + 3, where ? is an integer, has a prime factor of the same form. Which of these numbers is an example showing that Andrew s statement is false? A 19 B 33 C 85 D 91 E 99 Solution: D ? [SMC 2013 Q15] For how many positive integers ? is 4? 1 a prime number? A 0 B 1 C 2 D 3 E infinitely many Solution: B ? 5

Divisibility Proofs Show that the sum of any three consecutive integers is a multiple of 3. Que Problemo? He hasn t shown it s true for all possible integers.? Kyle s proof: 5 + 6 + 7 = 18, which is divisible by 3 . We could represent 3 consecutive integers as: ? ? + ? ? ? + ? Then: ? + ? + ? + ? + ? = ?? + ? = ?(? + ?) ? which is divisible by 3.

Divisibility Proofs How could I algebraically represent: 2? + 1 ? ? An odd number 2? An even number 2? + 1, 2? + 3 Two consecutive odd numbers ? (but 2? 1 and 2? + 1 might make your subsequent algebra easier) ?2+ ? + 12 The sum of the squares of two consecutive numbers. ? 2? ? ? A power of 2. 5? 1 One less than a multiple of 5.

Check Your Understanding Prove that the sum of three consecutive even numbers is a multiple of 6. 2? + 2? + 2 + 2? + 4 = 6? + 6 = 6(? + 1) which is a multiple of 6. ? Prove that the product of two consecutive odd numbers is always one less than a multiple of 4. 2? + 3 2? + 1 = 4?2+ 8? + 3 = 4 ?2+ 2? + 3 Which is 3 more than a multiple of 4, i.e. 1 less than a multiple of 4. Alternatively: ? 2? + 1 2? 1 = 4?2 1 Which is clearly one less than a multiple of 4.

Exercise 2 Prove that the difference between two consecutive cubes is one more than a multiple of 6. ? + ?? ?? = ??+ ???+ ?? + ? ?? = ???+ ?? + ? = ?? ? + ? + ? The product of two consecutive integers is even, thus ??(? + ?) is divisible by 6. Prove algebraically that the sum of two consecutive odd numbers is divisible by 4. ?? + ? + ?? + ? = ?? + ? = ?(? + ?) ? 1 Q1 ? [GCSE] I think of two consecutive integers. Prove that the difference of the squares of these integers is equal to the sum of the two integers. Two numbers are: ? and ? + ? Difference of squares: ? + ?? ??= ?? + ? Sum of numbers: ? + ? + ? = ?? + ? These are equal. ? Q2 [IMO] Prove that there is exactly one sequence of five consecutive positive integers in which the sum of the squares of the first three integers is equal to the sum of the squares of the other two integers. ? ??+ ??+ ? + ?? = ? + ??+ ? + ?? ???+ ? = ???+ ??? + ?? ?? ??? ?? = ? ? + ? ? ?? = ? ? = ? ?? ? = ?? So ???+ ???+ ???= ???+ ??? is only solution. 2 Prove that the difference between the squares of two consecutive odd numbers is a multiple of 8. ?? + ?? ?? ?? = ???+ ?? + ? ??? ?? + ? = ???+ ?? + ? ???+ ?? ? = ?? which is divisible by 8. Q3 ? ? [JMO] Find a rule which predicts exactly when five consecutive integers have sum divisible by 15. ? + ? + ? + ? + ? + ? + ? + ? + ? = ?? + ?? = ?(? + ?) Thus to be divisible by 15, ? + ? must be divisible by 3, i.e. the middle number of the five numbers must be divisible by 3. Q4 Prove that the product of four consecutive numbers is one less than a square number. ? ? + ? ? + ? ? + ? + ? = ??+ ? ??+ ?? + ? + ? = ??+ ???+ ????+ ?? + ? = ??+ ?? + ? 3 ? ? ?

Digit Proofs I think of a two-digit number. I then reverse the digits. Prove that the difference between the two numbers is a multiple of 9 e.g. 71 17 = 54 Let ab be a two digit number. Then its reverse is ba . The value of each number is 10? + ? and 10? + ? respectively. Model Problem Algebraically ? Thus their difference is 10? + ? 10? + ? = 9? 9? = 9(? ?) which is a multiple of 9. Manipulate to reach conclusion ? (Note how factoring out the 9 is a good explicit way to show the expression is a multiple of 9)

Test Your Understanding What would be the value of the 4-digit number with digits "???? ? ????? + ???? + ??? + ? a ? What would be the value if its digits were reversed? b ????? + ???? + ??? + ? ? What is the sum of these two numbers? c ????? + ???? + ???? + ????? ? Hence prove that the sum of a four digit number and its reverse is a multiple of 11. = ??(??? + ??? + ??? + ???) ? d

Rubbish Proofs Darth Kitty s solution: Pick the number 31 for example. The reverse of this is 13. And 31 13 = 18, which is divisible by 9. Hence the statement is true. What is wrong with their proof? Showing something is true for one example is not sufficient. We need to show the statement is true for ANY POSSIBLE starting number we choose. ?

Rubbish Proofs Photoshop Kitty s solution: Here s all possible two-digit numbers: 11 11 = 0, 12 12 = 0, ... 21 12 = 9, 22 22 = 0, 32 23 = 9, 42 24 = 18, ... 98 89 = 9, 99 99 = 0 These are all divisible by 9. What is wrong with their proof? Technically it s a valid proof, because we ve shown the statement is true for every possible two-digit number. But it s bad maths having to list out every case, and would become difficult if for example we tried to generalise the statement to 3-digit numbers. ?

Proof of 9 divisibility rule Prove for 2-digit numbers that if the sum of the digits of a number is a multiple of 9, then the number itself is divisible by 9. How to represent a two digit number ? with digits "??": ? = ??? + ? ? How do we represent property that digits add up to a multiple of 9? ? + ? = ?? ? How do we combine these equations to therefore show that the original number ? is a multiple of 9? ? = ??? + ? = ?? + ? + ? = ?? + ?? = ? ? + ? Hence ? is divisible by 9. ?

Exercise 3 Digit Problems [JMO] Observe that 49 = 4 x 9 + 4 + 9 Use algebra to find all other two-digit numbers which are equal to the product of their digits plus the sum of their digits. ??? + ? = ?? + ? + ? ?? = ?? Given ? is not 0: ? = ? Thus numbers are ??,??, ,?? Prove that there are no three-digit numbers which are equal to the product of their digits plus the sum of their digits. ???? + ??? + ? = ??? + ? + ? + ? ??? + ?? = ??? But since ?? is at most 81, ?? > ?? and thus ??? > ??? and hence the LHS is always greater. I think of a 3-digit number and then reverse its digits. Prove that the difference between these two numbers is a multiple of 11. If a number has the digits ??? then its reverse is "??? . Each number has the value ???? + ??? + ? and ???? + ??? + ?. ???? + ??? + ? ???? + ??? + ? = ??? ??? = ?? ?? ?? 4 Q1 ? ? [IMO] All the digits of a certain positive three-digit number are non-zero. When the digits are taken in reverse order a different number is formed. The difference between the two numbers is divisible by eight. Given that the original number is a square number, find its possible values. Difference of ??? and "??? is ??(? ?) Since 99 is not divisible by 8, ? ? is. Only possible if ? = ?,? = ? or vice versa. Only square in former case is 169. Only square in latter case is 961. ? Q2 b ? 5 Can you prove the 9 divisibility rule for 3 digit numbers? A divisibility test for 7 is to subtract twice the last digit from the remaining numbers, and see if the result is divisible by 7. e.g. 392 -> 39 4 = 35, which is clearly divisible by 7, so 392 is. Prove this works for all three- digit numbers. Let our number be n with the digits abc . ? = ???? + ??? + ?. If we subtract twice the last digit from the remaining numbers, we get 10a + b 2c. Now if this is divisible by 7, 10a + b 2c = 7k for some integer k. Thus ???? + ??? ??? = ??? Then n = 100a + 10b + c = 70k + 21c = 7(10k + 3c) which is divisible by 7. [IMO] An unfortunate number is a positive integer which is equal to 13 times the sum of its digits. Find all unfortunate numbers. (Hint: start with 2 digit first) For two-digit ??? + ? = ?? ? + ? ?? + ??? = ? which is impossible. Using same approach for 3- digit: 117, 156, 195 Need to also show not possible for more than 3 digits. Q3 ? ?

Another Example of Good/Bad Proofs [IMO] An arithmetic sequence is one in which the difference between successive terms remains constant (for example, 4, 7, 10, 13, ). Suppose that a right- angled triangle has the property that the lengths of its sides form an arithmetic sequence. Prove that the sides of the triangle are in the ratio 3:4:5. Example of a bad proof: What would a good proof look like? If the sides of the triangle are in the ratio 3:4:5, we could have any multiple of this. e.g. 6, 8, 10. These are still in an arithmetic sequence and satisfy Pythagoras Theorem. Use our general structure for an algebraic proof! Assume that the sides form an arithmetic sequence. Model this assumption, using algebraic expressions for side lengths that represent all possible arithmetic sequences, e.g. a-b, a, a+b. Do some manipulation using Pythagoras... Therefore, the sides have ratio 3:4:5. ? Why is it bad? We re supposed to be showing that IF the sides form an arithmetic sequence THEN the sides have ratio 3:4:5. They ve just shown the reverse! ?

QED QED is short for the latin Quad erat demonstrandum . It translates roughly to Which had to be demonstrated . Its symbol in maths is ? ? ? I think of a two-digit number. I then reverse the digits. Prove that the difference between the two numbers is a multiple of 9. Let the number have the digits ab . Then the number is 10a + b. If we reverse the digits to get ba , which has the value 10b + a. Subtracting to find the difference: 10a + b (10b + a) = 9a 9b = 9(a-b). 9(a-b) is divisible by 9.

Without loss of generality I think of a two-digit number. I then reverse the digits. Prove that the difference between the two numbers is a multiple of 9. Let the number have the digits ab . Then the number is 10a + b. If we reverse the digits to get ba , which has the value 10b + a. Subtracting to find the difference: 10a + b (10b + a) = 9a 9b = 9(a-b). 9(a-b) is divisible by 9. When we find the difference between two numbers we tend to do the bigger number subtracting the smaller number. Here in our proof we did ?? ?? . If this difference is positive what have we assumed? That ? ? ? If we stated this assumption that ? ?, have we made our proof less general , in the sense that we ve only now proved the property for restricted two-digit numbers where the first digit is greater than (or equal to) the second? No, it doesn t matter, because if we had say ??, then after we d reversed the digits to get 75, we could have subtracted the other way round. The proof still implicitly covers all two-digit numbers because the original number and the reversed number are interchangeable when we come to subtract. ?

Without loss of generality I think of a two-digit number. I then reverse the digits. Prove that the difference between the two numbers is a multiple of 9. Let the number have the digits ?? . Without loss of generality, let ? ?. Then the number is 10? + ?. If we reverse the digits to get ba , which has the value 10b + a. Subtracting to find the difference: 10a + b (10b + a) = 9a 9b = 9(a-b). 9(a-b) is divisible by 9. Without loss of generality (or w.l.o.g. for short) means that we have assumed a specific case, but this doesn t make the proof any less general .

Other Types of Proof Games [Source: JMO] X and Y play a game in which X starts by choosing a number, which must be either 1 or 2. Y then adds either 1 or 2 and states the total of the two numbers chosen so far. X does likewise, adding either 1 or 2 and stating the total, and so on. The winner is first player to make the total reach (or exceed) 20. i) Explain how X can always win. 12 For (i), what do we actually have to show? That for any way in which Y plays, we can always find a resulting move that guarantees us to win. ?

Summary So what makes a good (and valid!) proof? 1. Use of algebra: a) When appropriate, use variables to represent something that could take any value (e.g. the two digits!) This keeps your argument as general as possible. b) Then use algebra to manipulate these variables based on the question. 2. Keep things general! Avoid making assertions that would ignore certain possibilities. 3. Don t make leaps of logic Try not to assume too much. You need to clearly show your steps without making assumptions, which may turn out to be wrong! 4. Avoid circular arguments If the statement to prove is something like If X, then show that Y , then your proof needs to be something like: Assume that X, then [manipulation involving X]... And thus Y is true. You can t assume Y is true at any point, because that s what you re trying to prove! 5. Consider edge cases Consider unusual cases. e.g. What if the first digit is 0? What if the digits are the same? Does our proof still work? 6. Avoid listing out lots of cases If you re having to list out lots and lots of cases, then you re possibly missing ways to narrow down your search. Could you use algebra?