\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{1}{February 17, 1995}

\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$.

\begin{proof}

By induction on $k$.
\begin{enumerate}
\item
{\bf Base case:} $k$ = $0$. 
\[ F_{k+2} = F_{2} = F_{1} +F_{0} = 1+0 = 1, \mbox{    and  }
1+ \sum_{i=0}^k F_i = 1+F_0 = 1+0 =1.\]
Therefore, the claim is true for $k=0$.

\item
{\bf Inductive Step:} 

Show that for any positive integer $k$, if the claim is true for $k$
then the claim must also be true for $k+1$.

Fix any $k\geq 0$.
If the claim is true for $k$, then 
$ \displaystyle 1+ \sum_{i=0}^k F_i = F_{k+2}. $\\
We show that the claim for $k+1$ must therefore also be true:
\[ 1+ \sum_{i=0}^{k+1} F_i 		
= 1+\sum_{i=0}^{k} F_i + F_{k+1}	
= F_{k+2} +F_{k+1}
= F_{k+3} = F_{(k+1)+2}	
\]
Here, the second equality follows from the inductive hypothesis, and the third
equality from the definition of Fibonacci numbers. 
\end{enumerate}
Therefore, by induction,
$ \displaystyle 1 + \sum_{i=0}^{k}F_i=F_{k+2} \;$
for all integers $k\geq 0$.
\end{proof} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\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}}$.

\begin{proof}
By induction on $n$.
To simplify notation, let us define 
\[
a_n \equiv \underbrace{ \sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}_{n \; \mbox{1's}}.
\] So the problem is to prove that $a_n$ is irrational for all integers $n>1$.

\begin{enumerate}
\item
{\bf Base case:} $n$ = $2$. 

We showed in class that $a_2 = \sqrt{1+1} = \sqrt{2}$ is irrational.  

\item
{\bf Inductive Step:} 

Show that for any integer $n\geq 2$, if the claim is true for $n$ 
then the claim must also be true for~$n+1$.

If the claim is true for $n$, then $a_n$ is irrational.
We must prove that $a_{n+1}$ is also irrational.
We prove this by contradiction.
If $a_{n+1}$ is a rational number, then 
$a_{n+1} = p/q$ for some integers $p$ and~$q$.
Since $a_{n+1} = \sqrt{1+a_n}$, we have 
$a_n = {p^2}/{q^2} - 1 = (p^2-q^2)/q^2$,
a rational number, which is a contradiction.
%	\begin{eqnarray*}
%	\sqrt{1+a_n} & = & \frac{p}{q} \\
%	1+a_n & = & \frac{p^2}{q^2}  \\
%	a_n &= & \frac{p^2}{q^2} -1
%	\end{eqnarray*} 
We conclude that $a_{n+1}$ must be irrational. 

\end{enumerate}
Therefore, by induction, $a_n$ is irrational for all integers $n >1$.
%\[
%a_n \equiv \underbrace{ \sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}_{n \; \mbox{1's}}
%\mbox{	   	is irrational}.\]
\end{proof}

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

Define the binomial coefficient 
$\displaystyle {n \choose k} =\frac{n!}{k!\,(n-k)!}\;$ 
for $0\leq k\leq n$.  \\
$0!$ is defined to be $1$.
The binomial coefficient is defined to be $0$ if $k<0$ or $k>n$. 

\bparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%  part a
\ppart 
For any integers $n$ and $k$ such that $0\le k\le n$,
\[
{n\choose k} = {n-1 \choose k} + {n-1 \choose k-1}.
\]

\begin{proof}
We may verify this directly using the formula given.
As mentioned in class, the equality holds  only for $n>0$.
\begin{eqnarray*}
{n-1 \choose k}+{n-1 \choose k-1} & = & 
\frac{(n-1)!}{k!\,(n-1-k)!} + \frac{(n-1)!}{(k-1)!\,(n-k)!}\\
& = & \frac{(n-1)!}{(k-1)!\,(n-1-k)!} 
	\cdot \left( \frac{1}{k}+ \frac{1}{n-k}\right) \\
& = & \frac{(n-1)!}{(k-1)!\,(n-1-k)!} \cdot \frac{n}{k(n-k)} \\
& = & \frac{n!}{k!\,(n-k)!} \\
& = & {n \choose k}
\end{eqnarray*}
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%  part b
\ppart
For any nonnegative integers $n$ and $m$,
\[
\sum_{k=0}^n {k\choose m} = {n+1 \choose m+1}.
\]

\begin{proof}
For any fixed integer $m$, we will do induction on $n$.

\begin{enumerate}
\item {\bf Base case:} $n$ = $0$. \\
If $m=0$, then %$\displaystyle 
\[
\sum_{k=0}^n {k\choose m}
		= \sum_{k=0}^0 {k\choose 0}
		= { 0 \choose 0} = 1 \;\mbox{ and }\;
%$\displaystyle 
{n+1 \choose m+1} = { 1 \choose 1} =1.
\]
If $m>0$, then %$\displaystyle 
\[
\sum_{k=0}^n{k \choose m} = {0 \choose m} = 0 \;\mbox{ and }\;
{n+1 \choose m+1} = {1\choose m+1} = 0
\]
by definition, since $0<m$ and $1<m+1$.

\item {\bf Inductive Step:} 
Show that for any integer $n\geq 0$, if the claim is true for $n$ 
then the claim must also be true for~$n+1$.

If the claim is true for $n$, then 
$\displaystyle \sum_{k=0}^n {k\choose m} = {n+1 \choose m+1}$.

We then have 
\[ \displaystyle \sum_{k=0}^{n+1} {k\choose m} 
= \sum_{k=0}^n {k\choose m} + {n+1 \choose m}
= {n+1 \choose m+1} + {n+1 \choose m}
= {n+2 \choose m+1}.	\]
Here the second follows from the inductive hypothesis and the third
equation follows from the result of part {\bf (a)}. 
\end{enumerate}

Therefore, by induction, 
$\displaystyle \sum_{k=0}^n {k\choose m} = {n+1 \choose m+1}$
for any nonnegative integers $n$ and $m$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{proof}
\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.

\begin{proof}

First let us prove this for positive integers: $n \geq 1$. 
Clearly, we will use induction on $n$. 
\begin{enumerate}
	\item
	{\bf Base case:} $n$ = $1$. Given.

	\item
	{\bf Inductive Step:} Assume the claim is true for $n$:
	$\sin n \theta$ and $\cos n\theta$ are rational.

	Prove the claim for $n+1$:
 	\[ \sin (n+1) \theta = \sin (n \theta + \theta)
	= \sin n \theta \cos \theta + \cos n \theta \sin \theta\]
	\[\cos (n+1) \theta = \cos (n \theta + \theta)
	= \cos n \theta \cos \theta - \sin n \theta \sin \theta\]
Since $\sin \theta, \cos \theta, \sin n \theta $ and $\cos n\theta$ are
all rational, and the rationals are closed under addition and multiplication, 
it follows that $\sin (n+1) \theta $ and $\cos (n+1) \theta$ are rational.
\end{enumerate}
This proves the theorem for positive integers.

Since $\sin( -n )\theta = - \sin n \theta$ and
 $\cos( - n )\theta = \cos n \theta$, 
$\sin n \theta$ and $\cos n\theta$ should be rational for 
all integers $n \leq -1$. For $n=0$, 
$\sin 0 =0$ and $\cos 0 =1$ are clearly rational. Therefore,for all 
integers $n$, $\sin n \theta$ and $\cos n\theta$ are rational.
\end{proof}

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

\begin{proof}
By induction on $k$.
\begin{enumerate}
	\item
	{\bf Base case:} $k$ = $0$. 
	We have $3^{2k}+4^{k+1} = 1+4 = 5$, which is divisible by 5.
	\item
	{\bf Inductive Step:} Show that for any positive integer $k$,
	if  $5$ divides $3^{2k}+4^{k+1}$, then 
	$5$ divides $3^{2(k+1)}+4^{(k+1)+1}$.

	\[3^{2(k+1)}+4^{(k+1)+1} = 9\cdot 3^{2k} + 4\cdot 4^{k+1} 
	= 4\cdot (3^{2k}+4^{k+1}) + 5\cdot 3^{2k}.\]
If $5$ divides $3^{2k}+4^{k+1}$, then
$5$ divides $4\cdot (3^{2k}+4^{k+1}) + 5\cdot 3^{2k}$.
\end{enumerate}
We conclude  that $5$ divides $3^{2k}+4^{k+1}$ for all integers $k \geq 0$.
\end{proof}

\end{problems}

\end{document}
