\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{1}{February 9, 1995}{In recitation, February 17}

{\bf Reading:} Chapter 1 of {\it Discrete Mathematics for Computer Scientists}
by J.K. Truss.

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Let $F_i$ be the $ith$ Fibonacci number; that is, 
\[ 
F_0=0, \; F_1=1, \; \mbox{ and } \; F_i=F_{i-1}+F_{i-2},\;\mbox{ for } i\geq 2.
\] 
Show that 
$ \displaystyle
1 + \sum_{i=0}^{k}F_i=F_{k+2}\;
$
for all $k\geq 0$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Prove that for each integer $n > 1$, the expression
\[
\underbrace{ \sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}_{n \; \mbox{1's}}
\]
is irrational. For example, for $n=2$ this is $\sqrt{1+\sqrt{1}}$.
You may assume that $\sqrt{2}$ is irrational.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Define the binomial coefficient 
$\displaystyle {n \choose k} =\frac{n!}{k!\,(n-k)!}\;$ 
for $0\leq k\leq n$.  This is read ``$n$ choose $k$,'' and is the number
of ways of choosing $k$ distinct objects from a set of $n$ distinct objects.
(Although you can't use this fact in your proofs unless you prove it first.)
Don't forget that $0!$ is defined to be $1$.
The binomial coefficient is defined to be $0$ if $k<0$ or $k>n$. 

Show that 
\bparts
\ppart \hspace{.5in} $\displaystyle 
	{n\choose k} = {n-1 \choose k} + {n-1 \choose k-1}\;$ 
       for any integers $n$ and $k$ such that $0\le k\le n$, and
\ppart \hspace{.5in}
	$\displaystyle \sum_{k=0}^n {k\choose m} = {n+1 \choose m+1}$
       for any nonnegative integers $n$ and $m$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Let $\theta$ be an angle for which $\sin \theta$ and $\cos \theta$ are
rational.  Prove that for all integers $n$, 
$\sin n \theta$ and $\cos n\theta$ are rational.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Show that $5$ divides $3^{2k}+4^{k+1}$ for all integers $k \geq 0$.



\end{problems}

\end{document}
