Concepts of Mathematics (21-127) — Feedback on Homework 5

Homework 5 was due on Thursday 27th February 2014. I graded Q2,4 and the grader graded Q1,3,5. All questions are marked out of 6.

Question 1. The biggest problem with this question was mis-stating the induction hypothesis; the problem was similar to Question 2, see below.

Question 2. Many of the errors arising in this question were the same as have arisen in previous induction questions. Instead of pointing out all the errors, I'll list how some things should/should not be done:

• When you state $P(n)$, $n$ should not be quantified. $P(n)$ is a variable proposition in $n$, so in particular it must depend on the value of $n$. If you say 'for all $n$' then the dependence on $n$ is gone, because you could replace every instance of $n$ by another letter and the meaning would not change, and it would become meaningless to substitute in a value of $n$... for example, if $P(n)$ is "for all $n \in \mathbb{N}$ ...stuff..." then $P(3)$ is "for all $3 \in \mathbb{N}$ ...stuff...", which is weird (and wrong).
• Your induction step should start from your highest base case. Most people proved $P(18), P(19), P(20)$ as their base cases, and so your induction hypothesis should start with "let $k \ge 20$ be arbitrary". The reason for this is that $P(k+1)$ should be the "smallest unproved step".
• Some people tried to do this by weak induction, sometimes successfully, sometimes unsuccessfully, but in any case the weak inductive proof was ugly (and you were asked to use strong induction, so alarm bells should have been ringing).

Question 3. The errors in this question mostly arose through lack of justification. For instance, in the proof that $a \mid b$ and $b \mid a$ implies $a= \pm b$, people often said $b=qa$ and $a=q'b$ for some $q,q' \in \mathbb{Z}$, and then said $qq'=1$ without really justifying it. Another common error, in the proof that $a|b \Rightarrow a \le b$ when $a,b > 0$, was assuming that $q>0$ when $aq=b$. This is true, but requires proof! (It's easy: just divide by $a$ and use closure of the order-relation $<$ on $\mathbb{Q}$ under multiplication by positive numbers!)

Question 4. The easiest way to do this question was to show that the sets of common divisors of each of the three pairs of numbers are equal. (If they have the same common divisors then they certainly have the same greatest common divisors!) Say $$X = \{ \text{common divisors of}\ a+b\ \text{and}\ a-b \}$$ $$Y = \{ \text{common divisors of}\ 2a\ \text{and}\ a-b \}$$ $$Z = \{ \text{common divisors of}\ a+b\ \text{and}\ 2b \}$$ Now, by far the easiest way to do this would be to prove $X \subseteq Y \subseteq Z \subseteq X$, i.e. 3 containments. To my surprise some people chose instead to prove $X \subseteq Y \subseteq X$ and $Y \subseteq Z \subseteq Y$ (or something along those lines), i.e. 4 containments, and some people went to the extent of proving 6 containments... don't create work for yourself! Proving transitivity of $\subseteq$ is very easy, meaning that the 3-containment proof is quickest. Some people tried to do this without using set containment, which was often fine, but some of these arguments were very vague and referred only to divisibility and not to being the greatest common divisor.

Question 5. This problem was typically done well by those who realised which theorem to apply. The most common error was failing to do the second part of the question which, by the way, was false: for instance, $6 \mid 30$ and $10 \mid 30$ but $6 \times 10 = 60 \not \mid 30$.

Back to course page