%hw3.tex: Homework assignment 3
%%a Plain TeX file by Doron Zeilberger

%begin macros
\nopagenumbers
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros

\centerline
{
\bf Dr. Z.'s Number Theory Homework assignment 3
}




{\bf 1.} Write down $F_n$ for $ 1 \leq n \leq 10$.

{\bf 2.} List all the 1-2 walks from $0$ to $7$. Count them and make sure that you get $f_7=F_8$.

{\bf 3.} Prove the following identities (using the fact that $F_n$ is a linear combination of $\alpha^n$ and $\beta^n$
where $\alpha, \beta= \frac{1 \pm \sqrt{5}}{2}$.

{\bf a.}
$$
F_{n+3} - F_{n} =2 F_{n+1}  \quad .
$$


{\bf b.}
$$
F_{n-2} + F_{n+2} =3 F_{n}  \quad .
$$

{\bf c.}
$$
F_{n+4} - F_{n+3} + 2F_{n+2}- 3F_{n+1}-3F_{n}=0  \quad .
$$

{\bf 4.} Use the combinatorial model (in terms of paths) to prove that for every positive integer $n$,
$$
F_{m+n+1}=F_{m+1}F_{n+1} + F_{m}F_{n} \quad .
$$

{\bf 5.} Give a Zeilberger-style proof of the following identities, using the provided $N_0$

{\bf a.}
$$
F_{n+1}F_n -F_{n-1}F_{n-2} = F_{2n-1} \quad, \quad N_0=5 \quad .
$$

{\bf b.}
$$
\sum_{i=1}^{2n-1} F_i F_{i+1} = F_{2n}^2 \quad, \quad N_0=5 \quad .
$$



\end
