## Archive for the ‘Cambridge teaching’ Category

December 9, 2013

This post is intended as a footnote to one that I wrote a couple of years ago about the meaning of “implies” in mathematics, which was part of a series of posts designed as an introduction to certain aspects of university mathematics.

If you are reasonably comfortable with the kind of basic logic needed in an undergraduate course, then you may enjoy trying to find the flaw in the following argument, which must have a flaw, since I’m going to prove a general statement and then give a counterexample to it. If you find the exercise extremely easy, then you may prefer to hold back so that others who find it harder will have a chance to think about it. Or perhaps I should just say that if you don’t find it easy, then I think it would be a good exercise to think about it for a while before looking at other people’s suggested solutions.
(more…)

### A look at a few Tripos questions X

May 29, 2012

Since time is short, I am going to discuss a couple of Groups questions but in slightly less detail than I have been giving up to now: instead of working through the questions completely, I’ll try to zero in on the most important points. Because there wasn’t a separate Groups course until 2008, I am taking my questions from that year.

5E. For a normal subgroup $H$ of a group $G$, explain carefully how to make the set of (left) cosets of $H$ into a group.

For a subgroup $H$ of a group $G$, show that the following are equivalent:

(i) $H$ is a normal subgroup of $G$;

(ii) there exist a group $K$ and a homomorphism $\theta:G\rightarrow K$ such that $H$ is the kernel of $\theta$.

Let $G$ be a finite group that has a proper subgroup $H$ of index $n$ (in other words, $|H|=|G|/n$). Show that if $|G|>n!$, then $G$ cannot be simple. [Hint: Let $G$ act on the set of left cosets of $H$ by left multiplication.]
(more…)

### A look at a few Tripos questions IX

May 26, 2012

Exam day approaches, so I’ve decided to prioritize. Instead of doing question 7C, which isn’t all that interesting (in the sense that it doesn’t give me much scope to emphasize principles of more general use in exams), I’m going to skip it, and instead, if I get time, go through a groups question or two. But first I will do the final Numbers and Sets question because it involves something a lot of people dislike: the inclusion-exclusion principle. It’s worth getting comfortable with this, because it comes up year after year (either in Numbers and Sets or in Probability). You may think that applying the principle requires some ingenuity. The aim of this post is to convince you that it can be done on autopilot.

8C. Let $X$ be a finite set with $n$ elements. How many functions are there from $X$ to $X$? How many relations are there on $X$?

Show that the number of relations $R$ on $X$ such that, for each $y\in X$, there exists at least one $x\in X$ with $xRy$, is $(2^n-1)^n$.

Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations $R$ for which, in addition, for each $x\in X$, there exists at least one $y\in X$ with $xRy$, is

$\displaystyle \sum_{k=0}^n(-1)^k\binom nk(2^{n-k}-1)^n$.
(more…)

### A look at a few Tripos questions VIII

May 24, 2012

Now for a question on modular arithmetic. As with countability, there is a very high chance of a question on this topic. [Added after the post was written: as usual I wrote down my thoughts about this question as I had them, and I didn't spot the best approach to part (ii) of the question until after I had come up with some less good approaches. So my recommendations evolve through the post, with some of the later ones superseding some of the earlier ones.]

6C. (i) Prove Wilson’s theorem: if $p$ is prime then $(p-1)!\equiv -1$ (mod $p$).

Deduce that if $p\equiv 1$ (mod 4) then

$\displaystyle \Bigl(\bigl(\frac{p-1}2\bigr)!\Bigr)^2\equiv -1$ (mod $p$).

(ii) Suppose that $p$ is a prime of the form $4k+3$. Show that if $x^4\equiv 1$ (mod $p$) then $x^2\equiv 1$ (mod $p$).

(iii) Deduce that if $p$ is an odd prime, then the congruence

$\displaystyle x^2\equiv -1$ (mod $p$)

has exactly two solutions (modulo $p$) if $p\equiv 1$ (mod 4), and none otherwise.
(more…)

### A look at a few Tripos questions VII

May 20, 2012

The obligatory question on countability/uncountability.

5C. Define what is meant by the term countable. Show directly from your definition that if $X$ is countable, then so is any subset of $X$.

Show that $\mathbb{N}\times\mathbb{N}$ is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any $n\geq 1$, $\mathbb{N}^n$ is countable.

A function $f:\mathbb{Z}\to\mathbb{N}$ is periodic if there exists a positive integer $m$ such that, for every $x\in\mathbb{Z}$, $f(x+m)=f(x)$. Show that the set of periodic functions $f:\mathbb{Z}\to\mathbb{N}$ is countable.
(more…)

### A look at a few Tripos questions VI

May 11, 2012

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.
(more…)

### A look at a few Tripos questions V

May 8, 2012

Here is the final analysis question from 2003.

12C. State carefully the formula for integration by parts for functions of a real variable.

Let $f:(-1,1)\to\mathbb{R}$ be infinitely differentiable. Prove that for all $n\geq 1$ and for all $t\in(-1,1)$,

$\displaystyle f(t)=f(0)+f'(0)t+\frac 1{2!}f''(0)t^2+\dots$
$\displaystyle \dots+\frac 1{(n-1)!}f^{(n-1)}(0)t^{n-1}+\frac 1{(n-1)!}\int_0^tf^{(n)}(x)(t-x)^{n-1}dx$.

By considering the function $f(x)=\log(1-x)$ at $x=1/2$, or otherwise, prove that the series

$\displaystyle \sum_{n=1}^\infty\frac 1{n2^n}$

converges to $\log 2$.
(more…)

### A look at a few Tripos questions IV

May 2, 2012

This post belongs to a series that began here. Next up is a question about integration.

11B. Let $f:[a,b]\to\mathbb{R}$ be continuous. Define the integral $\int_a^bf(x)dx$. (You are not asked to prove existence.)

Suppose that $m, M$ are real numbers such that $m\leq f(x)\leq M$ for all $x\in [a,b]$. Stating clearly any properties of the integral that you require, show that

$\displaystyle m(b-a)\leq\int_a^bf(x)dx\leq M(b-a)$.

The function $g:[a,b]\to\mathbb{R}$ is continuous and non-negative. Show that

$\displaystyle m\int_a^bg(x)dx\leq\int_a^bf(x)g(x)dx\leq M\int_a^bg(x)dx$.

Now let $f$ be continuous on $[0,1]$. By suitable choice of $g$ show that

$\displaystyle \lim_{n\to\infty}\int_0^{1/\sqrt{n}}nf(x)e^{-nx}dx=f(0)$,

and by making an appropriate change of variable, or otherwise, show that

$\displaystyle \lim_{n\to\infty}\int_0^1nf(x)e^{-nx}dx=f(0)$.
(more…)

### A look at a few Tripos questions III

April 30, 2012

Here’s another one.

10F. State without proof the Integral Comparison Test for the convergence of a series $\sum_{n=1}^\infty a_n$ of non-negative terms.

Determine for which positive real numbers $\alpha$ the series $\sum_{n=1}^\infty n^{-\alpha}$ converges.

In each of the following cases determine whether the series is convergent or divergent:

(i) $\displaystyle \sum_{n=3}^\infty \frac 1{n\log n}$,

(ii) $\displaystyle \sum_{n=3}^\infty \frac 1{n\log n(\log\log n)^2}$,

(iii) $\displaystyle \sum_{n=3}^\infty \frac 1{n^{1+1/n}\log n}$.
(more…)

### A look at a few Tripos questions II

April 28, 2012

This is the second in a series of posts that started here. In the first post I explained what I’m up to. Now let me just continue with some more questions. I’m now on to the harder Section II questions. Here’s the first one I want to look at. Even though it makes the posts shortish, I think I’m going to stick to one long question per post.

9F. Prove the Axiom of Archimedes.

Let $x$ be a real number in $[0,1]$ and let $m,n$ be positive integers. Show that the limit

$\displaystyle \lim_{m\to\infty}[\lim_{n\to\infty} \cos^{2n}(m!\pi x)]$

exists, and that its value depends on whether $x$ is rational or irrational.

[You may assume standard properties of the cosine function provided they are clearly stated.]
(more…)