CIS-375 Help Session Note 1 (Spring 2020)

11 Feb 2020

Scire ad trascendere - Learn to transcend.

Topics covered:

• Boolean logic, truth tables
• Understanding and using definitions
• Divisibility and fundamental theorem of artithmetic
• Proof of if-then and iff statements

Develop the ability to understand new concepts

In the future, no matter where you are going to work in (e.g. industry, academia, etc.), you are likely to encounter new concepts. During undergraduate education, you are taught with general knowledge, which acts as a foundation for your further specialization. There are too many technologies in this world to be covered within a four-year time span. Therefore, instead of teaching you everything, it would be much more practical if we choose to cultivate an ability to understand everything individually.

One of the key purposes of this course is to help you form the skills to comprehend mathematical concepts that are necessary for all computer science literature. Personally speaking, I think mathematical concepts are the “easiest” to understand among all other categories, simply because:

1. They are usually very concise.
2. They usually exclude any possible ambiguity.
3. It is very easy to verify whether one has understood the concept correctly or not.

More concretely, the definition of a simplest mathematical concept looks like this:

A circle is a shape consisting of all points in a plane that are a given distance from a given point, the centre. (Wikipedia)

Whereas in psychology, the definition of a fundamental concept looks like this:

Emotions are biological states associated with the nervous system brought on by neurophysiological changes variously associated with thoughts, feelings, behavioural responses, and a degree of pleasure or displeasure. (Wikipedia)

There is no doubt that the mathematical concept possesses higher degree of clarity and definitiveness. Therefore, please do not be afraid of new concepts in mathematics. After all, they are not the most difficult things you’ll need to deal with in your future studies.

Identifying the key components of a definition

Having finished grading your homework, I find out that many of you are unable to understand the definitions provided by the homework guidelines effectively. The sentence structure or wording in mathematical materials may differ from standard English documents, which perhaps creates difficulty for you to perceive an idea. However, the fact that these contents tend to be grammatically correct implies that they contain all essential components that build up a sentence, i.e. subject, verb, object, complements, etc. To understand a concept thoroughly, I think the first thing you need to do is to identify what each component is. Let’s look at the examples below.

You may begin to notice that “\(A\) is said to be \(B\) if \(C\)” is a very common expression in mathematical literature. In this case, usually \(A\) is the subject, \(B\) is the name of the definition, and \(C\) the predicate for determining whether \(A\) can be called \(B\). For Pythagorean triples, \(A\) is \((a,b,c)\), \(B\) is “Pythagorean triple”, and \(C\) is \(a^2 + b^2 = c^2\). For even numbers, \(A\) is \(n\), \(B\) is “even number”, and \(C\) is \(2 \mid n\). It is essentially saying: if \(C\) is true, then \(A\) is \(B\). Otherwise, \(A\) is not \(B\).

Let’s come back to Toyota number, which appears in the homework question. The definition of Toyota number is as follows:

Let \(n\) be a positive integer. Then \(n\) is said to be a Toyota number if \(3 \mid n^2 + 5n\).

Here, \(A\) is \(n\), \(B\) is “Toyota number” and \(C\) is \(3 \mid n^2 + 5n\). If \(3 \mid n^2 + 5n\ (C)\) is true, then \(n\ (A)\) is a “Toyota number (\(B\))”. Otherwise, if \(3 \mid n^2 + 5n\ (C)\) is false, then \(n\ (A)\) is not a “Toyota number (\(B\))”. It is important to realize that the subject here is \(A\) instead of \(C\). Therefore, we are trying to decide whether \(n\) is a Toyota number, not \(3 \mid n^2 + 5n\) or \(n^2 + 5n\).

In question 2b, you are asked to prove/disprove if “the product of two Toyota numbers is a Toyota number.” Let there be two Toyota numbers \(m\) and \(n\), you should determine if \(mn\) is a Toyota number. Some people try to calculate if \((m^2 + 5m)(n^2 + 5n)\) is a Toyota number, which is completely irrelevant to what the question is asking.

Converting definitions to something easier to comprehend

Sometimes definitions are written in a most compact and concise form, which can increase the difficulty to understand them. When you find a new definition confusing, maybe you can try to convert them to “everyday language”, which greatly facilitates problem solving. For example, we mentioned the definition of Toyota numbers before:

A positive integer \(n\) is said to be a Toyota number if \(3 \mid n^2 + 5n\).

It is easy to see that \(n^2 + 5n = n(n+5)\), which means that we can check if \(3 \mid n(n+5)\) instead.

The fundamental theorem of arithmetic states that every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, except for the order of the factors. With this knowledge in our mind, we can conduct the following derivation:

1. If \(3 \mid n^2 + 5n\), it means that 3 is a factor of \(n^2 + 5n\).
2. \(n^2 + 5n = n(n+5)\). The fundamental theorem of arithmetic indicates \(n\) and \(n+5\) can both be represented as the product of prime numbers (now assume \(n > 1\)).
3. 3 is a prime number. If 3 is a factor of \(n(n+5)\), then either 3 is a factor of \(n\) or 3 is a factor of \(n+5\) (or both).

You may find the third step a bit obscure. You can think about it in this way: suppose 3 is not a factor of \(n\) nor \(n+5\), there is no way that 3 is a factor of \(n(n+5)\), because you cannot find two integers other than \(1\) and \(3\) whose product is 3.

With the conclusion of step 3, we can rewrite the definition of Toyota number as follows:

A positive integer \(n\) is said to be a Toyota number if either \(n\) is divisible by 3 or \(n+5\) is divisible by 3 (or both). ²

It is a lot longer and much easier to understand. But you know what? Mathematicians hate it. So everyone one them will prefer the old definition.

The definition of square free integers is even trickier:

Let \(n\) be a positive integer. Then \(n\) is said to be a square free integer if \(n\) is divisible by no perfect square other than 1.

Many of you are unable to tell whether a number is square free or not, because the definition is simply too abstract. For example, some of you consider 12 to be a square free integer, which is not true because \(4 \mid 12\), and 4 happens to be a perfect square. Here comes the question: using the fundamental theorem of arithmetic, can you “simplify” the definition of square free integers? I will provide the answers below, but feel free to think about it for now.

Answer (click to expand)

The fundamental theorem of arithmetic states that we can write \(n\) as the product of its prime factors. That is, we can write

\[n = p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n},\]

where \(p_i\)’s are its prime factors and \(e_i\)’s are exponents greater than zero. For example, we can write \(60=2^2 \times 3 \times 5\), \(2 \times 3^2 \times 5\), etc.

Now it should be fairly easy to see that \(n\) is a square free number if none of the exponents are greater than 1! Because if any exponent \(e_j\) is greater than 1, then \(n\) would be divisible by a perfect square \(p_j^2\). This allows us to rewrite the definition of square free numbers as follows:

Let \(n\) be a positive integer. Then \(n\) is said to be a square free integer if all exponents of its prime factors are equal to one. ³

This definition also provides a way of examining whether an integer is square free or not. For example, because \(2310 = 2 \times 3 \times 5 \times 7 \times 11\), we know that it is a square free number; because \(2520 = 2^3 \times 3^2 \times 5 \times 7\), it is not a square free number. Isn’t this definition much easier to understand?

Therefore, when you come across a definition that is obscure, try to convert it into a form which you can handle with ease. I know there are a lot of unspoken techniques involved in this process, so it is vitally important that you do more exercises to perfect your skills.

Learn the foundation of proofs

In my opinion, a proof is a formal argument to show that a mathematical statement is true. Once you get familiar with writing proofs, it almost feels like a novelist writing his new piece. As a result, everyone can have his/her unique way of presenting an elegant proof, as long as the logic is consistent. However, despite being a highly malleable form of argument, there are still some basic rules to follow. Just like a novel can be of any topic, but it always needs to have characters, plot, theme, etc.

There are many well-known templates to write proofs, such as proof by contradiction, proof by induction and so on. I believe we may get to these advanced methods later in this semester, but they are not required at this stage. Now we are only constructing direct proofs, which has little constraint. However, there is one case where special care should be taken, that is when you are proving iff statements. Always remember that you need to prove both directions of an iff statement!

Find a correct direction

Usually, you are asked to either prove/disprove a statement. These are two distinct directions, and only one of them is correct. Therefore, it is important to have an idea of whether the statement itself is actually true/false. If it seems to be true, we will prove it to be true (using direct proofs). It is seems to be false, then we can disprove it (with counterexamples).

One of the easiest ways to figure out if a statement is true or not is to test it with examples. An example is shown as below.

During the trial-and-error phase, if you have tested a number of cases, and the statement still holds true, then you should consider proving the statement to be true.

Remember the purpose of proving is to show that the statement is always true, given the constraints. It only takes one counterexample to disprove a statement, but to prove something, you need to convince everyone that the statement is perpetually correct. Therefore, you cannot prove a statement by examples, because it is usually impossible to enumerate all possible cases (except for some special cases where the number of possibilities is finite, e.g. Boolean logic).

Think about the well-known Goldbach’s conjecture, which states that “every even integer greater than 2 can be expressed as the sum of two primes.” For example, \(6=3+3\), \(8=3+5\), \(10=3+7\), \(12=7+5\), etc. People have tested all even numbers from 2 to 4,000,000,000,000,000,000 with computers, and the conjecture is true for all these numbers. But this doesn’t mean that this conjecture is proved, because the program can never test all possible even numbers. However, if the program finds one even number that cannot be represent as the sum of two primes, then we can immediate disprove this conjecture that has puzzled some of the most talented mathematicians around the world for hundred of years.

Just let it be

To this day, I still remember the catchphrase of my high school math teacher–when we had difficulty solving a question, he would always say “顺其自然”, which basically means “let it be”. In a mathematical context, it means to approach a question with what you have in hand, even when it seems very distant from what is being asked. It is somehow correct because all these exam/homework questions are designed in a way that they are solvable for an average student. Right now, you are not dealing with read-world problems. You are just solving questions that are meticulously created for students, which are supposed to be easy. If you are greatly confused by these questions, it only means that you are not familiar with the techniques taught in class.

With this attitude in mind, let’s look at the most difficult problem in homework #2, which is to prove/disprove “the product of two Toyota numbers is a Toyota number.” The first step is to figure out whether the statement is true or not. To do that, we need to find some Toyota number. With the new Toyota number definition above, we can immediately enumerate these Toyota numbers: 1, 3, 4, 6, 7, 9, … And then we can start the testing phase. We can quickly verify that \(3 \mid (3 \times 4)^2 + 5 \times (3 \times 4)\), \(3 \mid (4 \times 7)^2 + 5 \times (4 \times 7)\), \(3 \mid (6 \times 9)^2 + 5 \times (6 \times 9)\), so we should consider proving this statement instead of disproving it.

Let \(m\), \(n\) be two Toyota numbers, then by definition, we know that \(3 \mid m^2 + 5m\) and \(3 \mid n^2 + 5n\). Now we need to find out if the product of these two Toyota numbers (which is \(mn\), not \((m^2 + 5m)(n^2 + 5n)\)) is a Toyota number. Using the definition of Toyota numbers, we can say that our goal is to determine if \(3 \mid (mn)^2 + 5mn\) is true.

Right now, there is not much to work with, as all statements we have are discriminative rather than quantitative. More specifically, \(3 \mid m^2 + 5m\) just tells you “3 divides \(m^2 + 5m\)”, but there is not a value or equality that you can play with. Recall the definition of divisibility indicates that there exists an integer \(k_1\) such that \(m^2 + 5m = 3k_1\). Similarly, there is another integer \(k_2\) such that \(n^2 + 5n = 3k_2\). We have gone from nothing to something, namely two equalities to work with:

\[\begin{align*} m^2 + 5m &= 3k_1,\\ n^2 + 5n &= 3k_2. \end{align*}\]

Our goal is to prove \(3 \mid (mn)^2 + 5mn\). Here, \((mn)^2\) is a quadratic term, which is difficult to deal with. If we look at the two equalities, it is not hard to observe that

\[\begin{align*} m^2 &= 3k_1 - 5m,\\ n^2 &= 3k_2 - 5n, \end{align*}\]

which means we can substitute the quadratic terms with linear terms. This can bring us closer to form of the second term (\(5mn\)) in the target, maybe there is a chance for something magical to happen. Therefore, we can write

\[\begin{align*} (mn)^2 + 5mn &= m^2n^2 + 5mn\\ &= (3k_1 - 5m)(3k_2 - 5n) + 5mn\\ &= 9k_1k_2 - 15k_1n - 15k_2m + 25mn + 5mn\\ &= 9k_1k_2 - 15k_1n - 15k_2m + 30mn\\ &= 3(k_1k_2 - 5k_1n - 5k_2m + 10mn). \end{align*}\]

Because \(k_1k_2 - 5k_1n - 5k_2m + 10mn\) is an integer, by the definition of divisibility, we can conclude that \(3 \mid (mn)^2 + 5mn\), which means \(mn\) is a Toyota number.

The thought process of the solution is clear:

1. Find out if we should prove or disprove the statement.
2. Write down our target.
3. Derive a step further from what we have known to generate two equalities to work with.
4. Compare our target and the equalities, then find a way to combine them.
5. The result shows that the statement is true.

I think the “let it be” spirit can be reflected vividly in this process. When you don’t know whether to prove or disprove, you just test the statement with cases to find a general direction. When there is no equation to work with, you create something out of nowhere. When you do have something in your hand, you go ahead and figure out a way to combine them so that you can unravel the answer that is carefully hidden by the test maker. Try to play with the knowledge in your head and rearrange the equations on your draft paper. At some point, you will come up with something constructive.

If you are not that good at observing…

In the proof above, there is a “clever step” where we substitues the \((mn)^2\) term with the product of two linear terms. What if you are unable to devise it on your own? In the discussion above, we have shown that the definition of Toyota numbers is equivalent to:

A positive integer \(n\) is said to be a Toyota number if either \(n\) is divisible by 3 or \(n+5\) is divisible by 3 (or both).

Let \(m\), \(n\) be two Toyota numbers, there are only four possibilities:

1. $3 \mid n, 3 \mid m$
2. $3 \mid (n + 5), 3 \mid m$
3. $3 \mid n, 3 \mid (m + 5)$
4. $3 \mid (n + 5), 3 \mid (m + 5)$

What do we do next? We’ll have to verify them one by one!

1. If \(3 \mid n, 3 \mid m\), we can write \(n = 3k_1, m=3k_2\), then \(mn = 9k_1k_2\). It can be seen that

   \[\begin{align*} (mn)^2 + 5mn &= (9k_1k_2)^2 + 5 \cdot (9k_1k_2)\\ &= 81k_1^2k_2^2 + 45k_1k_2\\ &= 3(27k_1^2k_2^2 + 15k_1k_2). \end{align*}\]

   Hence, we know that \(mn\) is a Toyota number in this case.

2. If \(3 \mid (n + 5), 3 \mid m\), we can write \(n + 5 = 3k_1, m = 3k_2\). Therefore, \(n = (3k_1 - 5)\) and \(mn = 3k_2(3k_1 - 5)\). It can be seen that

   \[\begin{align*} (mn)^2 + 5mn &= \left[3k_2(3k_1 - 5) \right]^2 + 5 \cdot \left[3k_2(3k_1 - 5)\right]\\ &= 9k_2^2(3k_1 - 5)^2 + 15k_2(3k_1 - 5)\\ &= 3\cdot \left[ 3k_2^2(3k_1 - 5)^2 + 5k_2(3k_1 - 5) \right] \end{align*}\]

   Hence, we know that \(mn\) is a Toyota number in this case.

3. If \(3 \mid n, 3 \mid (m + 5)\), similar to Case 2, we know that \(mn\) is a Toyota number in this case.

4. If \(3 \mid (n + 5), 3 \mid (m + 5)\), we can write \(n + 5 = 3k_1, m + 5= 3k_2\). Therefore, \(n = (3k_1 - 5)\) and \(m = (3k_2 - 5)\). Now, we have \(mn = (3k_1-5)(3k_2-5)\). It can be seen that

   \[\begin{align*} (mn)^2 + 5mn &= \left[(3k_1-5)(3k_2-5)\right]^2 + 5 \cdot \left[(3k_1-5)(3k_2-5)\right]\\ &= (3k_1-5)(3k_2-5) \left[ (3k_1-5)(3k_2-5) + 5 \right]\\ &= (3k_1-5)(3k_2-5) (9 k_{1} k_{2} - 15 k_{1} - 15 k_{2} + 30)\\ &= 3 (3k_1-5)(3k_2-5) (3 k_{1} k_{2} - 5 k_{1} - 3 k_{2} + 10). \end{align*}\]

   Hence, we know that \(mn\) is a Toyota number in this case.

We have shown that \(mn\) is a Toyota number in all four possible cases. Therefore, \(mn\) is always a Toyota number.

There are always multiple ways to solve a question. Of course, this approach is more complicated than the previous one, but it is still a valid proof that can get you full marks. If you just try to play with the information given by the question, you will get yourself closer to one of the correct paths and eventually come up with a valid solution.

Beyond this help session…

If you want to do better in course, try these:

1. Read the textbook carefully.
2. Finish some practice questions on textbook.
3. If you find it difficult to solve homework questions, feel free to come to office hours.
4. Access different types of resources. For example, learn from YouTube, Coursera, etc.
5. Rewrite proofs that you did in course activities and office hours to consolidate your impression.