\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb,fullpage}
\begin{document}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\section*{CS 70 homework 3 submission}
Your full name: PUT YOUR NAME HERE
\\
Your login name: PUT YOUR LOGIN NAME HERE
\\
Homework 3
\\
Your section number: PUT YOUR SECTION NUMBER HERE
\\
Your list of partners: LIST THE PEOPLE YOU WORKED WITH HERE (OR ``none'')
\begin{enumerate}
\item
Let $f(n)$ be defined by the recurrence relation
$f(n) = 7 f(n-1) - 10 f(n-2)$ (for all $n \ge 2$)
and $f(0)=1$, $f(1)=2$.
Prove using strong induction that $f(n)=2^n$ for every $n\in \N$.
YOUR ANSWER GOES HERE.
\item
Prove by induction that, if the bucket initially contains a finite number
of marbles at the start of the game,
then the game will end after a finite number of moves.
YOUR ANSWER GOES HERE.
\item
Prove that any game of Dots-and-lines that starts with $d$ dots
consists of at most $3d$ moves before someone loses.
YOUR ANSWER GOES HERE.
\item
Let $H(n)$ denote the the total number of handshakes that have
occurred among the $n$ people by the time this process is finished
and everyone is seated at the same table.
Prove that it doesn't matter what order the bartender decides to
choose tables; we always have $H(n) = n(n-1)/2$.
YOUR ANSWER GOES HERE.
\item
Consider the following recursive algorithm for solving this problem:
\begin{tabbing}
FindPair$([x_1,\dots,x_n],y)$:\\
1. \=If $n<2$, then return NotFound.\\
2. \>If $x_1+x_n=y$ then return $(x_1,x_n)$.\\
3. \>If $x_1+x_n>y$ then return FindPair$([x_1,\dots,x_{n-1}],y)$.\\
4. \>If $x_1+x_n