\documentclass[11pt]{report}
\usepackage{times}
\pagestyle{empty}
\def\nl{\hspace*{\fill}\\}
\def\bs{\hspace*{-1.2em}}
\def\bd{\begin{description}}
\def\ed{\end{description}}
\def\ra{\rightarrow}
\def\ul{\underline}
\def\0{_{\phantom0}}
\setlength{\parindent}{0em}
\setlength{\parskip}{1ex}
\pagestyle{empty}
\addtolength{\textwidth}{1in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\textheight}{2in}
\addtolength{\topmargin}{-1in}
\begin{document}
\begin{center}
{\bf Freshman Seminar 24i: Mathematical Problem Solving}
\\
Some induction problems
\end{center}
1. It can be shown\footnote{
  Let $v$ be the left-most vertex (or one of them if there's a choice),
  and $v', v''$ its neighbors along the boundary of $P$.  If $v' v''$
  is an interior diagonal, we are done.  Else there is an interior
  diagonal $v w$ for some other vertex $w$ in the triangle forme by
  $v,v',v''$; for instance, we may choose for~$w$ the vertex in that
  triangle, other than $v,v',v''$, that is closest to~$v$.
  Thanks to Zach, our resident computational geometer,
  for finding this construction.  Where did we use $n>3$?

  With some more care we can even use this construction to prove
  that $P$\/ has an ``interior'', that is, the fact (which I relegated
  in class to an application of the Jordan curve theorem) that $P$\/
  splits the plane into exactly two connected regions, an ``interior''
  and an ``exterior'' of~$P$.
  }
  that every planar $n$-gon ($n>3$)~$P$\/ has an ``interior diagonal''
  --- that is, two nonconsecutive vertices $V,V'$ such that
  the line segment joining $V,V'$ is contained in the interior of~$P$.
  Use this to prove that the interior angles of $P$\/ total
  $(n-2) 180^\circ$ (a.k.a.\ $(n-2) \pi$ radians).
  [Which version of induction is natural to use here?]

2. Recall that $n \choose k$ is the binomial coefficient
(a.k.a.\ combinatorial coefficient) defined by
$$
{n \choose k} = \frac{n!}{k! \, (n-k)!} \, ;
$$
if $k<0$ or $k>n$ we set ${n \choose k} = 0$.

i) Given $k\geq 0$ and $n\geq k$, what is
${k \choose k} + {k+1 \choose k} + {k+2 \choose k}
+ \cdots + {n \choose k}$?
\nl
ii) [somewhat trickier] Given $k\geq 2$ and $n\geq k$, what is
$$
\frac1{{k \choose k}}
+ \frac1{{k+1 \choose k}}
+ \frac1{{k+2 \choose k}}
+ \cdots
+ \frac1{{n \choose k}}?
$$

3. For $n>0$ and $d \geq 0$, how many monomials of total degree~$d$\/
are there in $n$ variables?  For example, when $d=n=3$
the number is~$10$: using variables $x,y,z$ we find the cubic monomials
$$
x^3,\;x^2y,\;x^2z,\;xy^2,\;xyz,\;xz^2,\;y^3,\;y^2z,\;yz^2,\;z^3.
$$
(In particular the answer is not simply $n \choose d$:
that's the number of \hbox{degree-$d$}\/ monomials in which
no variable appears to power greater than~$1$.)

4. Give a formula for
$(\cos x) \, (\cos (2x)) \, (\cos (4x)) \, (\cos (8x)) \cdots (\cos (2^n x))$.
[Especially if you're seeing this for the first time,
you might try to use the same trick to evaluate other products such as
$
\prod_{n=1}^{89} \cos(n^\circ)
= \cos(1^\circ) \cos(2^\circ) \cos(3^\circ) \cdots \cos(89^\circ),
$
or to construct a problem along the same lines involving
$f(x) f(3x) f(9x) f(27x) \cdots f(3^n x)$ for some function~$f$.]

5. [An IMO problem, but it's from the Easiest IMO Ever,
and we weren't told there that this was an induction problem \ldots]
Find the integer solution $(x,y)$ of $(x^2 + xy - y^2)^2 = 1$
that has the largest value of $x^2 + y^2$ subject to the conditions
$0 \leq x \leq 1981$, \, $0 \leq y \leq 1981$.

(Follow-up: what can you say about the Diophantine equation\footnote{
  That is, an equation to be solved in integers;
  Diophantus originally worked with rational numbers,
  but that can always be encoded into integer solutions as well
  by replacing an equation in rational numbers $r_1,r_2,\ldots,r_n$
  by a homogeneous equation in integers $x_0,x_1,x_2,\ldots,x_n$
  where $r_i = x_i / x_0$ for each $i=1,2,\ldots,n$.
  }
$(x^2 + 4xy - y^2)^2 = 1$?)

6. [Thanks to Sonal Jain for suggesting this one]
For a $S$\/ set of $n$ (distinct) positive numbers,
let $\Sigma(S) = \{ \sum_{t\in T} t \mid T \subseteq S \}$;
that is, $\Sigma(S)$ is the set of positive numbers that can be written
as the sum of some (possibly empty) subset $T \subseteq S$.
Given $n$, how small can the cardinality $\#(\Sigma(S))$ be?
For example, if $n=1$ or $n=2$ then all $2^n$ sums are distinct,
and for $n=3$ there can be at most one coincidence among the $2^3$
sub-sums (if the largest element of~$S$\/ is the sum of the other two);
so the minimal cardinality is $2,4,7$ for $n=1,2,3$ respectively.

\end{document}

