A look at a few Tripos questions VI

I’m now going to turn to the Numbers and Sets questions from the same year, 2003. I’ve lost count of the number of times I’ve heard people say that the course is quite easy but the questions on the examples sheets and exams are very hard and “not very closely related to the course”. There is a grain of truth in that: the new concepts you have to grasp in Numbers and Sets are not as difficult as the new concepts you have to grasp in most of the other courses, so in order to give enough substance to Tripos questions the examiners are almost forced to put in a significant problem-solving element. However, certain styles of problem occur quite regularly, so it’s good to get a bit of practice. And perhaps a detailed discussion of the 2003 questions will be helpful as well. As I did with Analysis I, I’ll start with a post on the Section I questions and then I’ll have separate posts for each of the four Section II questions. The paper, by the way, is Paper 4.

1. (i) Prove by induction or otherwise that for every $n\geq 1$ ,

$\displaystyle \sum_{r=1}^nr^3=\Bigl(\sum_{r=1}^nr\Bigr)^2$

(ii) Show that the sum of the first $n$ positive cubes is divisible by 4 if and only if $n\equiv 0$ or $3$ (mod 4).

Part (i) could be an A-level question (I think). Is there a neat way to do it? I’ll think about the “or otherwise” possibility in a moment, but let’s go for the straightforward approach of using induction.

A non-neat approach would be to prove the well-known formula for the sum of the first $n$ positive integers and then prove by induction that the square of that, i.e., $n^2(n+1)^2/4$ , is the sum of the first $n$ positive cubes. But let’s see what happens if we just take the statement as it stands and try to prove it by induction. Here’s what I would write to start with.

The statement is certainly true when $n=1$ , since both sides equal 1. Now suppose that it is true for $n-1$ . Then it will be true for $n$ if

$\displaystyle n^3=\Bigl(\sum_{r=1}^nr\Bigr)^2-\Bigl(\sum_{r=1}^{n-1}r\Bigr)^2$

Hmm, that looks sort of promising because it we have a difference of two squares. So next I’d write this.

The right-hand side is a difference of two squares, and therefore equals $n\bigl(n+2\sum_{r=1}^{n-1}r\bigr)$ .

Now we don’t seem to have much alternative but to work out the sum of the first $n-1$ integers. We might as well use the standard trick.

But $2\sum_{r=1}^{n-1}r=\sum_{r=1}^{n-1}(r+n-r)=n(n-1)$ . Therefore, $n+2\sum_{r=1}^{n-1}r=n^2$ , which shows that the right-hand side is $n^3$ , as required.

I don’t know whether that was the best thing to do, but the point is that this question can be hacked out pretty quickly one way or another.

What about the second part? Well, the golden rule of Tripos questions applies, since it is related to the first part. Here goes.

By Part (i), it is enough to prove that the sum of the first $n$ positive integers is even if and only if $n\equiv 0$ or 3 (mod 4). To see this, note that $\sum_{r=1}^nr$ has the same parity as $\sum_{r=1}^{n-1}r$ when $n$ is even and different parity when $n$ is odd. Therefore, mod 2 the sums are 1, 1, 0, 0, 1, 1, 0, 0, and so on.

That completes the question. A quick remark is that what I wrote in that last paragraph might look slightly sloppy, because I didn’t set out a formal inductive argument. However, what I wrote (a) got to the heart of the matter and (b) clearly could be turned into a formal inductive argument. If you feel tempted to leave out details, you should be very sure that you know how to fill in those details, and that the examiner knows that you know how to fill them in, and that the reason you’ve left them out is that they are quite long to write out and genuinely uninteresting. It’s a judgment call, and I’d suggest erring on the safe side.

What about the “or otherwise”? A fact like that must surely have some reason for being true. It feels like one of those things that is true because of some picture of balls arranged in a “right-angled isosceles tetrahedron”. Except that that’s not quite correct, because the picture looks as though it needs to be four-dimensional.

Is there something we can count in two different ways, getting the left-hand side if we count one way and the right-hand side if we count the other way?

To get the right-hand side we could take the Cartesian product of two discrete right-angled triangles. More formally, we could take the set of all quadruples $(a,b,c,d)$ of non-negative integers such that $a+b\leq n$ and $c+d\leq n$ . But how do we relate that to a bunch of cubes?

Let’s try to find a nice set of points that gives us the bunch of cubes. We could take the set of all quadruples $(a,b,c,d)$ of positive integers such that $a\leq n$ and $b,c$ and $d$ are all at most $a$ .

Is there a nice bijection between these two sets? I can’t see one. I think I’m going to cheat and use the internet.

Done that, and although I found a pictorial proof, it was basically just a pictorial version of the above analytic proof, and therefore not very interesting. On to the second question.

2C. What is an equivalence relation? For each of the following pairs $(X,\sim)$ , determine whether or not $\sim$ is an equivalence relation on $X$ .

(i) $X=\mathbb{R}$ , $x\sim y$ iff $x-y$ is an even integer.

(ii) $X=\mathbb{C}\setminus\{0\}$ , $x\sim y$ iff $x\overline y\in\mathbb{R}$ .

(iii) $X=\mathbb{C}\setminus\{0\}$ , $x\sim y$ iff $x\overline y\in\mathbb{Z}$ .

(iv) $X=\mathbb{Z}\setminus\{0\}$ , $x\sim y$ iff $x^2-y^2$ is $\pm 1$ times a perfect square.

A first tip here is not to try to make guesses such as, “There’s bound to be at least one false statement.” Examiners have sometimes played evil tricks, but more importantly your aim here is to think about the mathematics. And since it’s a Section I question your starting assumption (which occasionally has to be revised) should be that the mathematics is pretty easy.

Let’s get started. First dilemma: how much can we assume when defining an equivalence relation? Is it enough to say, “An equivalence relation is a relation that is reflexive, symmetric and transitive?” Or do we need to define those three properties as well? And do we need to say what a relation is?

These questions don’t have very definite answers. The examiner was probably expecting candidates at least to define the three properties, but would probably have found it quite hard to remove marks for somebody who didn’t do so. Anyhow, since there are three options of increasing explicitness, I think I’ll compromise and go for the second.

An relation $R$ on a set $X$ is reflexive if $xRx$ for every $x\in X$ . It is symmetric if $xRy\implies yRx$ for every $x,y\in X$ . It is transitive if $xRy, yRz\implies xRz$ for every $x,y,z\in X$ . It is an equivalence relation if it is reflexive, symmetric and transitive.

I felt free to use the shorthand $xRy,yRz\implies xRz$ , since its meaning was very clear. One thing that was important was to demonstrate that I knew how the quantifiers worked. For instance, I didn’t just write, “ $R$ is symmetric if $xRy\implies yRx$ ,” but I added the words “for every $x,y\in X$ “.

Now to the more interesting part of the question. It’s pretty obvious that the first relation is an equivalence relation. Is there a quicker way of proving it than writing out some very obvious calculations? We might consider defining a partition, but perhaps, since the boring method isn’t too laborious, it’s better not to bother to think. Here’s the boring method.

(i) Let $x,y,z\in\mathbb{R}$ . Then $x-x=0$ , which is an even integer. If $x-y=2m$ for some integer $m$ , then $y-x=-2m$ . And if $x-y=2m$ and $y-z=2n$ , then $x-z=2(m+n)$ . Since $x,y,z$ were arbitrary, this shows that $\sim$ is reflexive, symmetric and transitive, so it is an equivalence relation.

Here’s how one might try to do it with partitions. Even if I don’t necessarily recommend this approach, I definitely recommend, as I’ve said before, at least considering using alternative definitions.

(i) For every real number $t$ in the interval $[0,2)$ , let $E_t$ be the set $\{t+2m:m\in\mathbb{Z}\}$ . Then the sets $E_t$ form a partition of $\mathbb{R}$ and $x\sim y$ if and only if $x$ and $y$ belong to the same cell of this partition. Therefore, $\sim$ is an equivalence relation.

Hmm … I don’t really like that, because I feel an obligation to prove that distinct $E_t$ really are disjoint and that every real number belongs to some $E_t$ . These statements, though not hard to prove, are hard enough to make this approach longer than the boring approach.

Now let’s look at the second example. There are two possibilities here. If you can’t immediately see whether this is an equivalence relation, then just dive in and do the calculations. You’ll end up writing something like this.

(ii) Let $x,y,z\in X$ . Then $x\overline x=|x|^2$ , which is a positive real number. If $x\overline y\in\mathbb{R}$ , then so is $y\overline x$ , since $y\overline x=\overline{x\overline y}$ . And if $x\overline y\in\mathbb{R}$ and $y\overline z\in R$ , then $(x\overline y)(y\overline z)=|y^2|x\overline z\in\mathbb{R}$ . Since $|y|^2$ is a non-zero real, $x\overline z\in\mathbb{R}$ . This shows that $\sim$ is an equivalence relation.

If you’re up on your complex numbers, you’ll recognise that the relation $x\overline{y}\in\mathbb{R}$ is saying that $x$ and $y$ belong to the same line through the origin. That would allow you to give a partitions proof.

(ii) Every non-zero complex number can be written uniquely in the form $re^{i\theta}$ for some $r>0$ and some $\theta\in[0,2\pi)$ . It can also be written uniquely in the form $re^{i\theta}$ with $r$ a non-zero real number (positive or negative) and $\theta\in[0,\pi)$ . If $x=re^{i\theta}$ and $y=se^{i\phi}$ are written in the second form, then $x\overline y=rse^{i(\theta-\phi)}$ , which is real if and only if $\theta=\phi$ . Therefore, $\sim$ is an equivalence relation.

Annoyingly, that again wasn’t as quick as I’d hoped, but it feels like a better explanation of why $\sim$ is an equivalence relation.

I counselled against trying to second guess the examiner, but here it really does seem likely that (iii) is going to be false, given its similarity to (ii). Why? Well, if the relation in part (iii) is an equivalence relation, then the proof that it is an equivalence relation will presumably be very similar to the proof in part (ii), and it would be very odd for the examiner to ask you to do essentially the same thing twice. This isn’t a completely conclusive argument, but it does suggest that we begin by looking for a counterexample.

It’s almost always a good idea with a question of this flavour to try the simplest thing you possibly can and work upwards. What’s the simplest non-zero complex number? I’d go for 1. So let’s take 1 for $x$ . Now we need $y$ such that $\overline y$ is real. The simplest example I can think of is 1. But that’s a problem, because we’re now not going to be able to find $z$ such that $y\overline z$ is an integer but $x\overline z$ is not. So a minimal requirement of our $y$ is that it should not equal $x$ .

Let us therefore backtrack to where we chose $y$ . We want the simplest non-zero complex number $y$ such that $\overline y$ is an integer and $y\ne 1$ . How about 2? What does that tell us we need of $z$ ? We need $2\overline z$ to be an integer, but $\overline z$ not to be an integer. That’s easy enough. The simplest number that has that property is $1/2$ , and we’re done.

Here’s what one would actually write out after those thoughts.

(iii) Let $x=1$ , $y=2$ and $z=1/2$ . Then $x\overline y=2\in\mathbb{Z}$ and $y\overline z=1\in\mathbb{Z}$ , but $x\overline z=1/2\notin\mathbb{Z}$ . Therefore, $\sim$ is not transitive and so not an equivalence relation.

One thing not to do is a technique that many people seem to like, which is to write out a proof, get to a step that doesn’t seem to hold in general, and argue that that is a proof that the result fails. Here’s what it might look like in this case. (Here I’m giving a model non-answer, so to speak.)

Hmm, I was just about to set out on that when I realized that I’d done something a little foolish, which was to assume that if the relation failed to be an equivalence relation then the problem would lie with transitivity. But actually it’s not even reflexive. So a better answer would have been this.

(iii) Since $(1/2)\overline{(1/2)}=1/4\notin\mathbb{Z}$ , the relation $\sim$ is not reflexive and is therefore not an equivalence relation.

However, let me try to give a model non-answer to the question “Is the relation $\sim$ transitive?” The right approach is to give a simple counterexample. The wrong approach is to write something like this.

Let $x,y,z\in X$ . If $x\overline{y}\in\mathbb{Z}$ and $y\overline z\in\mathbb{Z}$ , then $(x\overline y)(y\overline z)=|y|^2x\overline z$ . This shows that $|y|^2 x\overline z$ is an integer, but that doesn’t necessarily imply that $x\overline z$ is an integer. Therefore, $\sim$ is not transitive.

The trouble with what I’ve just written is that the failure of a proof attempt doesn’t prove that a result is false. It can, however, guide one to a proof. Here, for example, we see that we’re looking for an example where $|y|^2x\overline z$ is an integer but not $x\overline z$ . So it’s pretty natural to think of taking $y=2$ and then $x=z=1/2$ , which isn’t the same example as before but it’s very similar.

On to the fourth part. Here one can profitably use the information that this is a Section I question. This relation is obviously reflexive and symmetric, but there doesn’t seem to be a trivial proof that it is transitive. Why not? Because if $x^2-y^2=u^2$ and $y^2-z^2=v^2$ , then $x^2-z^2=u^2+v^2$ , and that doesn’t have to be a perfect square. Again, that’s a useful thought to have, but it doesn’t constitute an answer to the question. For all we know, $u^2$ and $v^2$ have to be very special kinds of perfect squares (because they are differences of squares), and perhaps if you add two of those very special squares together, you always get a perfect square.

This is where the fact that we’re doing a Tripos question comes in. If a statement like that were true, it would be a piece of serious number theory. This is a fraction of a Section I question, so we probably aren’t expected to come up with a piece of serious number theory (unless it’s very obvious bookwork, which this isn’t). So the result is probably false. So we should try to find a counterexample.

Our example can’t be too trivial — in particular, we need all three of $x$ and $y$ to be distinct to have any hope of its being a counterexample. Help, that means we need some Pythagorean triples. I can only think of 3,4,5 and 5,12,13. Ah, but I see a potentially useful feature of those, which is that they both contain the number 5. Can that somehow be worked into an example? I probably want to set $y=5$ since $y$ will be common to my two assumptions. So how about $x=3$ and $y=5$ ? That gives me that $x^2-y^2=-4^2$ , which is fine. And $z$ ? I might as well take 12 and see what happens? I get $y^2-z^2=5^2-12^2$ . Oops. OK, $z=13$ then. That’s better, $y^2-z^2=-12^2$ . Now, what is $x^2-z^2$ ? It is $9-169=-160$ , which, thankfully, is not plus or minus a perfect square.

Having thought of that, I can make it slightly neater by switching things round. Here’s what I’d write.

(iv) Let $x=13$ , $y=5$ and $z=3$ . Then $x^2-y^2=12^2$ and $y^2-z^2=4^2$ , but $x^2-z^2=160$ , which is not a perfect square. Therefore, $\sim$ is not transitive and so not an equivalence relation.

That part strikes me as medium hard for a Section I question — the kind of thing that many people would have spotted and many people would not have spotted. But maybe I’m wrong about that: you’re more or less forced to look for Pythagorean triples and then the first two such triples that we all know about from school do the job.

Update: It has subsequently occurred to me that my answer to (iv) was needlessly complicated. I could have used the same Pythagorean triple twice. For instance, setting $x=4, y=5$ and $z=3$ we get $x^2-y^2=3^2$ , $y^2-z^2=-4^2$ , but $x^2-z^2=7$ , which is not a perfect square.

12 Responses to “A look at a few Tripos questions VI”

RJ Evans Says:
May 11, 2012 at 10:32 am | Reply
Ahh… this takes me back.

I believe there is an erroneous “^2” at the end of the sentence beginning “The right-hand side is a difference of two squares…”

Many thanks — corrected now.
Anonymous Says:
May 11, 2012 at 10:36 am | Reply
I don’t know the Tripos, but in my experience “by induction, or otherwise” generally means “do it by induction, but we won’t penalize you if you know a trick we didn’t think of”
nugae Says:
May 11, 2012 at 1:24 pm | Reply
Your “otherwise”: Nicomachus, Introductio arithmetica, II.20, cited in Heath, A Manual of Greek Mathematics, Oxford, 1931. Take the first 1 odd numbers: they add up to 1³. Take the next 2 odd numbers: they add up to 2³. Take the next 3 odd numbers: they add up to 3³. And so on.

On the other hand, the first N odd numbers add up to N². Putting the two together gives the result, and with care it can be done without ever mentioning ½n(n+1).

For the details, see Heath. He also quotes al-Karkhī, who gives a presumably Greek-originated geometrical proof.
Friday Highlights | Pseudo-Polymath Says:
May 11, 2012 at 1:33 pm | Reply
[…] Hey! I thought Mr Gowers was done with the entertainment. There’s more fun! […]
Stones Cry Out - If they keep silent… » Things Heard: e220v5 Says:
May 11, 2012 at 1:36 pm | Reply
[…] Hey! I thought Mr Gowers was done with the entertainment. There’s more fun! […]
Fergal Daly Says:
May 14, 2012 at 4:18 pm | Reply
Here’s a pictorial proof of the sum of cubes being the square of sums, just using the fact that Sum(1..n) = n(n+1)/2.

Consider a square of side n(n+1)/2. If n is even, this is n/2 (n+1)s So you can lay n/2 (n+1)-sided squares across the top and the same along the right hand side and then fill in one more for the top right corner. You have now added n+1 (n+1)-sided squares.

If n is odd you can lay (n+1)/2 across the top (the last one sticks half-way out) and (n-1)/2 along the right-hand side (stopping short by half). So you have n (n+1) sided squares and and L-shape made out of 2 half-squares.

Here’s a picture of it

https://docs.google.com/spreadsheet/ccc?key=0AhbtqdywlrGadGFpaFQ4cGlveko3UUx0V3VINzhDYUE#gid=0

I’m curious how much credit this proof would get.
- Fergal Daly Says:
  May 14, 2012 at 4:21 pm
  Hmm, this seems to be the same proof as elsewhere, feel free to delete. I’m still curious if it would be an acceptable answer or is it too informal?
anonymous Says:
May 15, 2012 at 9:52 pm | Reply
Tim,

Is there a way to solve 1 without using the fact that $\sum_{k=1}^{n} k = n(n+1)/2$ .
- gowers Says:
  May 15, 2012 at 11:18 pm
  I think nugae has answered that question in his/her comment above.
anonymous Says:
May 17, 2012 at 2:02 am | Reply
Thank you. Here’s the link to Heath if anyone’s interested :
http://archive.org/details/cu31924008704219
PSmith Says:
November 22, 2012 at 9:02 pm | Reply
The “non-proof” that the relation in 2C(iii) fails to be transitive motivated the counterexample x = 1/2, y = 2, z = 1/2. But to my mind this is just a more convoluted proof that the relation is not reflexive: the conclusion is that NOT((1/2)~(1/2)).

Of course since the relation is symmetric but not reflexive it must fail to be transitive, but I am of the view that any triple (x,y,z) put forward as a counterexample to transitivity must have distinct values for x, y and z.

(There are a couple of misprints:

In the paragraph beginning “Our example can’t be too trivial”, “all three of x and y to be distinct” should probably read “all three of x and y and z to be distinct”.

In the update, there is a minus sign missing before 3^2 and an unwanted minus sign before 4^2.)
- PSmith Says:
  November 22, 2012 at 9:14 pm
  It also occurs to me that, having just done part (ii), the obvious line of thought for part (iii) would be “Does my answer for (ii) still work if I replace R with Z? No: |x|^2 is certainly real, but it doesn’t have to be an integer.”

Gowers's Weblog