%%
%% This is a LaTeX document
%%

\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}

%%
%% The margins I prefer
%%

\textwidth      = 15cm
\textheight     = 23cm
\oddsidemargin  = 0.46cm
\evensidemargin = 0.46cm
\topmargin      = -1cm
\parskip        = 10pt
\parindent      = 0pt

%%
%% German letters (doubled)
%%

\def\aa{{\mathfrak a}} 
\def\bb{{\mathfrak b}} 
\def\cc{{\mathfrak c}} 
\def\dd{{\mathfrak d}} 
\def\ee{{\mathfrak e}} 
\def\ff{{\mathfrak f}} 
\def\gg{{\mathfrak g}} 
\def\hh{{\mathfrak h}} 
\def\ii{{\mathfrak i}} 
\def\jj{{\mathfrak j}} 
\def\kk{{\mathfrak k}} 
\def\ll{{\mathfrak l}} 
\def\mm{{\mathfrak m}} 
\def\nn{{\mathfrak n}} 
\def\oo{{\mathfrak o}} 
\def\pp{{\mathfrak p}} 
\def\qq{{\mathfrak q}} 
\def\rr{{\mathfrak r}} 
\def\ss{{\mathfrak s}} 
%%\def\tt{{\mathfrak t}} 
\def\uu{{\mathfrak u}} 
\def\vv{{\mathfrak v}} 
\def\ww{{\mathfrak w}} 
\def\xx{{\mathfrak x}} 
\def\yy{{\mathfrak y}} 
\def\zz{{\mathfrak z}} 

\def\AA{{\mathfrak A}}
\def\BB{{\mathfrak B}}
\def\CC{{\mathfrak C}}
\def\DD{{\mathfrak D}}
\def\EE{{\mathfrak E}}
\def\FF{{\mathfrak F}}
\def\GG{{\mathfrak G}}
\def\HH{{\mathfrak H}}
\def\II{{\mathfrak I}}
\def\JJ{{\mathfrak J}}
\def\KK{{\mathfrak K}}
\def\LL{{\mathfrak L}}
\def\MM{{\mathfrak M}}
\def\NN{{\mathfrak N}}
\def\OO{{\mathfrak O}}
\def\PP{{\mathfrak P}}
\def\QQ{{\mathfrak Q}}
\def\RR{{\mathfrak R}}
\def\SS{{\mathfrak S}}
\def\TT{{\mathfrak T}}
\def\UU{{\mathfrak U}}
\def\VV{{\mathfrak V}}
\def\WW{{\mathfrak W}}
\def\XX{{\mathfrak X}}
\def\YY{{\mathfrak Y}}
\def\ZZ{{\mathfrak Z}}

%%
%% Blackboard Bold (triple)
%%

\def\AAA{{\mathbb A}} 
\def\BBB{{\mathbb B}} 
\def\CCC{{\mathbb C}} 
\def\DDD{{\mathbb D}} 
\def\EEE{{\mathbb E}} 
\def\FFF{{\mathbb F}} 
\def\GGG{{\mathbb G}} 
\def\HHH{{\mathbb H}} 
\def\III{{\mathbb I}} 
\def\JJJ{{\mathbb J}} 
\def\KKK{{\mathbb K}}
\def\LLL{{\mathbb L}} 
\def\MMM{{\mathbb M}} 
\def\NNN{{\mathbb N}} 
\def\OOO{{\mathbb O}} 
\def\PPP{{\mathbb P}} 
\def\QQQ{{\mathbb Q}} 
\def\RRR{{\mathbb R}} 
\def\SSS{{\mathbb S}} 
\def\TTT{{\mathbb T}} 
\def\UUU{{\mathbb U}} 
\def\VVV{{\mathbb V}} 
\def\WWW{{\mathbb W}} 
\def\XXX{{\mathbb X}} 
\def\YYY{{\mathbb Y}} 
\def\ZZZ{{\mathbb Z}} 

%%
%% Caligraphic letters (single)
%%

\def\A{{\cal A}} 
\def\B{{\cal B}} 
\def\C{{\cal C}} 
\def\D{{\cal D}} 
\def\E{{\cal E}} 
\def\F{{\cal F}} 
\def\G{{\cal G}} 
\def\H{{\cal H}} 
\def\I{{\cal I}} 
\def\J{{\cal J}}
\def\K{{\cal K}}
\def\L{{\cal L}} 
\def\M{{\cal M}} 
\def\N{{\cal N}} 
\def\O{{\cal O}} 
\def\P{{\cal P}} 
\def\Q{{\cal Q}} 
\def\R{{\cal R}} 
\def\S{{\cal S}} 
\def\T{{\cal T}} 
\def\U{{\cal U}} 
\def\V{{\cal V}} 
\def\W{{\cal W}} 
\def\X{{\cal X}} 
\def\Y{{\cal Y}} 
\def\Z{{\cal Z}} 

%%
%% Parentheses
%%

\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\def\>{\right\rangle}

%%
%% Renamings
%%

\def\of{\circ}
\def\union{\cup}
\def\intersect{\cap}
\def\d{\partial}

%%
%% Extras
%%

\def\smallmatrix#1#2#3#4{%
	\left({#1\atop #3}\;{#2\atop #4}\right)}
\def\mathllap#1{\mathchoice
{\llap{$\displaystyle #1$}}%
{\llap{$\textstyle #1$}}%
{\llap{$\scriptstyle #1$}}%
{\llap{$\scriptscriptstyle #1$}}}
\def\set#1#2{\left\{\,#1\mathllap{\phantom{#2}}\mathrel{}\right|\left.#2\mathllap{\phantom{#1}}\,\right\}}

\def\sgn{\mathop{\rm sgn}\nolimits}
\def\ord{\mathop{\rm ord}\nolimits}
\def\mod{\hbox{ mod }}


%%
%% Proof stuff
%%

\def\qed{\hfill\(\Box\)\smallskip}
\def\proof{{\bf Proof.\ \ }}

%%
%% Theorem types
%%

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}

%%
%% MAIN DOCUMENT
%%

\begin{document}
\begin{center}
\Large {\bf BMOC Mentoring Scheme}\\
\large Advanced Level -- Sheet 3\\
Possible Solutions\\
\end{center}
\vskip 40pt
\begin{enumerate}
\item {\it Find counting arguments to prove the following identities
(i.e. find something you can count in two different ways so that one
way is the LHS and the other is the RHS)}
\begin{enumerate}
\item ${n \choose s} = {n\over s}{n-1 \choose s-1}$

From a choice of $n$ people we will pick $s$ with one of them
special.  This can be done by picking all $s$ people (in $n \choose s$
ways) and then picking the special person from these (in $s$ ways).
Or by first picking the special person (in $n$ ways) and then picking
the rest (in $n-1 \choose s-1$ ways).
\item ${n\choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}$

This is just a generalisation of the previous one: From a choice of
$n$ people we will pick $r$ with $k$ of them special.
\item $\sum_{i=0}^n {n\choose i}{n\choose n-i} = {2n \choose n} =
\sum_{i=0}^n {n \choose i}^2$

Imagine picking $n$ people from a choice of $n$ men and $n$ women.  We
can either pick $i$ men and $n-i$ women (and sum) which gives the
LHS.  Or we can pick $i$ men and then pick $i$ women who won't be in
the group which gives the RHS.  In total we are picking $n$ people
from a choice of $2n$ which is the middle term.
\item ${n \choose s} = {n \over n-s} {n-1 \choose s}$

We choose a group of $s$ people from a choice of $n$ and then a
special person from the unselected people.  We do this by choosing the
$s$ people (in $n \choose s$ ways) and then the extra person (in $n-s$
ways).  Or by picking the extra person first (in $n$ ways) and then
the group (in $n-1 \choose s$) ways.
\item ${n\choose 0} + {n\choose 2} + \cdots = {n\choose 1} + {n\choose
3} + \cdots$

The LHS is the number of even subsets of $n$ elements and the RHS is
the number of odd subsets of $n$ elements.  A bijection between them
can be given as follows.  If an even subset contains the element $1$
then remove it, if not add it.
\item ${n\choose 0} + {n+1 \choose 1} + {n+2 \choose 2} + \cdots +
{n+r \choose r} = {n+r+1 \choose r}$

The RHS is the number of ways to choose $r$ objects from $n+r+1$
objects.  The LHS is the number of ways to do this if we assume $1$ is
not in the choice, $1$ is in but $2$ isn't, $1,2$ are in but $3$
isn't, ...
\end{enumerate}
\item {\it The following game is played on the integer points $(x,y)$ in
the plane with $x$,$y\ge 0$.  Initially, pieces are placed at $(0,0)$,
$(1,0)$ and $(0,1)$.  The following move is allowed: if the square
above and to the right of a piece are empty they can be filled with
pieces and the original piece removed.  Is it possible for the
initially occupied squares to all be simultaneously unoccupied?}

To the point $(a,b)$ assign the weight $2^{-a-b}$.  Initially the
weighted sum of the occupied squares is $2$.  It is easy to see that
the allowed move does not change the sum.  If the initial squares are
unoccupied then, in order to get the sum to be $2$ we need to occupy
all the other squares.  This is clearly impossible in a finite number
of moves.
\item {\it Show that there are either infinitely many composite numbers in
the sequence $2^{2^n}+1$ or infinitely many composite numbers in
$6^{2^n}+1$ (or both).}

Suppose that there are infinitely many primes in the $2^{2^n}+1$
sequence.  We need to show that there are lots of composites in the
other sequence.  Let $p = 2^{2^n}+1$ be a prime.  The {\bf order} of
an element $m$ modulo $p$ is the smallest power to which $m$ can be
raised to get $1$ modulo $p$.  In other words
$$m^{\ord(m)} \equiv 1 \mod p$$
By Fermat's little theorem we can see that the order of an element
must divide $p-1$.  In our case this means that the order of $6$
modulo $p$ must be a power of $2$, say $2^m$.  Thus
$$6^{2^m} \equiv 1 \mod p \quad\hbox{ but }\quad 6^{2^{m-1}}
\not\equiv 1 \mod p$$
Thus, $6^{2^{m-1}} \equiv -1 \mod p$ and so $6^{2^{m-1}} + 1$ is
divisible by $p$ (and clearly not equal to $p$) and hence is not a
prime.  For larger and larger $n$ this gives an infinite number of
composites in the $6^{2^m} + 1$ sequence.

{\bf Quadratic Reciprocity.}  There is a slightly easier way to do
this question which uses a very beautiful theorem of number theory.
As it is both very pretty and very useful I'll explain the basics
here.

The {\bf Legendre symbol} $\( a \over p \)$ for $p$ a prime and
$(a,p)=1$ is defined to be $1$ if $x^2 \equiv a \mod p$ has a solution
and $-1$ if it doesn't.  In other words, the Legendre symbol answers
the questions ``does $a$ have a square root?''.  There are two very
basic properties the symbol has:
$$\({ab \over p}\) = \({a \over p}\)\({b \over p}\) \quad\hbox{ and
}\quad \({a+p \over p}\) = \({a \over p}\)$$
Less obvious are the following two properties
$$\({a \over p}\) \equiv a^{(p-1)/2} \mod p \hbox{ (for odd $p$)},\quad
\({2 \over p}\) = \begin{cases}
1 & \hbox{if $p\equiv \pm 1 \mod 8$} \\
-1 & \hbox{if $p\equiv \pm 3 \mod 8$}
\end{cases}$$
And finally, the law of quadratic reciprocity (for 203 different
proofs go to {\tt
http://www.rzuser.uni-heidelberg.de/\~{}hb3/fchrono.html})
$$\({p \over q}\)\({q \over p}\) = \begin{cases}
1 & \hbox{if $p\equiv 1 \mod 4$ or $q\equiv 1 \mod 4$} \\
-1 & \hbox{if $p\equiv q\equiv 3 \mod 4$}
\end{cases}$$
This law is remarkably useful because it allows you to see if
something has a square root quite easily (repeatedly use quadratic
reciprocity and the multiplicative property).  For example, can you
use it to show that if $p=2^{2^n}+1$ then $6$ does not have a square
root (for $n\ge 1$)?  If you can then we know
$$6^{(p-1)/2} \equiv -1 \mod p$$
And so we can finish as in the first method.  Notice that this way we
know the exact value of $m$ whereas we didn't with the first method.
\item {\it Find a simple formula for the sum $\sum_{k=1}^n {n \choose k}
k^2$.}

This represents picking a committee from $n$ people with $2$ special
posts (which can be filled by the same person).  So, we should try to
count this in a different way (which doesn't involve summing).  If the
two posts are filled by the same person we could choose this person
(in $n$ ways) and then pick the rest of the committee (in $2^{n-1}$
ways --- a person is either in or out).  If the two posts are filled
by different people we could choose them (in $n(n-1)$ ways) and then
pick the rest of the committee (in $2^{n-2}$ ways).  Adding these
gives the answer $n(n+1)2^{n-2}$.
\item {\it Let $f(n)$ be a function defined on the set of positive integers
which takes values in the positive integers.  Prove that if
$$f(n+1) > f(f(n))$$
for each positive integer $n$ then $f(n)=n$.}

$f$ has a unique minimum at $n=1$ because, if $n>1$ then we have $f(n)
> f(f(n-1))$.  Once we know this, the same equation then shows that
the second smallest value is $f(2)$.  By induction we get
$$f(1) < f(2) < f(3) < \cdots$$
As $f$ takes values in the positive integers we already have $f(n) \ge
n$.  Suppose we have a $k$ such that $f(k)\ge k+1$.  Then $f(f(k)) \ge
f(k+1)$ which contradicts the assumed inequality for $f$.  So $f(n)=n$
for all $n$.
\item {\it Show that $n^7 - 77$ is never a Fibonacci number.}

We want to look at this modulo $p$ for some well chosen $p$.  Because
of the exponent being $7$ a good idea would be to have $\phi(p)$
divisible by $7$, so $p=29$ is perhaps a good choice.  We also want
the Fibonacci sequence to not take on too many values modulo $p$.
This also happens for $p=29$:
$$0,1,1,2,3,5,8,13,-8,5,-3,2,-1,1,0,\dots$$
Modulo $29$ the seventh powers are just $0,\pm 1, \pm 12$.  So the
values that $n^7-77$ takes are $-7,-2,9,10,11$.  None of these are in
the Fibonacci sequence so we are done.
\end{enumerate}
\end{document}