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

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

Question 1. There were a few common errors to this problem:

• Lots of people had problems writng down the contrapositive, converse, negation, etc... this is something you really should practice. Some people didn't answer the part of the question that asked about the converse (this was also a common problem on the test)... remember, do all parts of the question!
• Don't forget that when you write a rational number as the ratio of two integers, the denominator has to be nonzero: this is a condition you need to check each time.
• A lot of people ignored the hypothesis that $x \ne y$, leading to an incorrect counterexample of $x=y=\sqrt{2}$.

Question 2. There were a few common errors to this problem:

• A few people proved by induction that the claim held for all $n$ greater than or equal to some number. This was certainly part of the problem. But when you're asked to find 'the set of numbers for which it holds', that also entails finding the set of number for which it doesn't hold. (Why? Because excluding a number from your set is tantamount to saying that the claim doesn't hold for that number.) As such, you had to verify that the claim fails for all the preceding numbers too.
• A common error was to quantify $n$ in the statement of $P(n)$, or to say that the induction hypothesis holds 'for all $k$' or something along those lines. This is an issue that I will discuss in recitation, but the point is: $P(n)$ is a variable proposition involving $n$, so $n$ should not be quantified anywhere. Moreover, your induction hypothesis is a statement about some arbitrary and fixed $k \ge b$ (where $b$ is your base case); $k$ is fixed before you even start hypothesising anything, so it should not be quantified. (In fact, if you do say the IH holds 'for all $k$' then that's just assuming the end result!)
• A lot of people used inequalities in their deductions, like what was done in recitation. In recitation I justified each $\ge$ or $\le$ sign that I wrote—you should do that too.

Question 3. This question was mostly done well by everyone who used the fact proved in lectures that $\sum_{k=1}^n k = \frac{n(n+1)}{2}$. If you used this fact, then your induction step will have started out something like $$\sum_{k=1}^{n+1} k^3 = \sum_{k=1}^n k^3 + (n+1)^3 \overset{\mathrm{IH}}{=} \left( \sum_{k=1}^n k \right)^2 + (n+1)^3 = \frac{n^2(n+1)^2}{4} + (n+1)^3$$ What followed, except in a couple of cases, was a puddle of algebraic obscenity which, despite usually being correct, was very ugly. You could notice that there is a common factor of $(n+1)^2$. Factoring this out gives $$\frac{n^2(n+1)^2}{4} + (n+1)^3 = (n+1)^2\left[ \frac{n^2}{4} + n+1 \right] = (n+1)^2 \left[ \frac{n^2+4n+4}{4} \right] = \frac{(n+1)^2(n+2)^2}{4}$$ This isn't the most beautiful of all algebraic manipulations, but it's much shorter and easier to work with than expanding all the brackets.

Question 4. An alarming number of students in their induction step wrote down lines and lines of equations, deduced something true, and from the deduction that something was true, decided that was sufficient to prove the induction step. NO! If you want to do a load of algebra and deduce something true, this is only enough if you can reverse the steps! Though in many cases this was unnecessary; most people did this to prove that $\sqrt{n} + \frac{1}{\sqrt{n+1}} \ge \sqrt{n+1}$. This can be done directly using the observation that $\sqrt{n+1} > \sqrt{n}$ as follows; $$\sqrt{n} + \frac{1}{\sqrt{n+1}} = \frac{\sqrt{n}\sqrt{n+1}+1}{\sqrt{n+1}} > \frac{\sqrt{n}\sqrt{n}+1}{\sqrt{n+1}} = \frac{n+1}{\sqrt{n+1}} = \sqrt{n+1}$$

Question 5. This was an odd question, both to do and to mark. The main issue was that people wrote a paragraph of pure nonsense that even in English didn't make any sense. Typically, obfuscating your point isn't going to get you much credit. This was a difficult problem to put in words, but putting it in words was where the credit came! The issue was that the induction step is the assertion $\forall k \in \mathbb{N}\ (P(k) \Rightarrow P(k+1))$, however this fails here because the implication $P(1) \Rightarrow P(2)$ fails: you cannot deduce that any given two pens have the same colour from the assertion that every individual pen has the same colour as itself. If your answer didn't say something along these lines, or if it was unintelligible, it won't have received much credit.

Back to course page