\documentclass{article}
\usepackage{graphicx}
\usepackage[colorlinks=true,urlcolor=blue,linkcolor=blue,citecolor=blue]{hyperref}%
\usepackage{fancyhdr}
\usepackage[margin=35mm]{geometry}
\usepackage{amsmath}

\newcommand{\fn}[1]{\mathrm{#1}}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}

\lhead{\sf Logic and Mechanized Reasoning}
\rhead{\sf Fall 2021}

\begin{document}

\bigskip

\begin{center}
{\Large Assignment 2}

\medskip

due Thursday, September 9, 2021
\end{center}

\medskip

\thispagestyle{fancy}

\noindent Remember that homework is due at 6pm on the due date.

\subsection*{Problem 1 (3 points)}

Express the following using summation notation, and prove it by induction:
\[
\frac{1}{1\cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n \cdot (n + 1)} = \frac{n}{n+1}.
\]
(You can use notation like $\sum_{i \le n}$ or $\sum_{i = 1}^n$, as you prefer.)

\subsection*{Problem 2 (3 points)}

In class, we described an algorithm to solve the tower of Hanoi problem and proved
that $n$ disks can be moved from one peg to another with $2^n - 1$ steps. Prove, as clearly
as you can, that this is optimal: it is impossible to move $n$ disks from one peg
to another with a smaller number of steps.

\subsection*{Problem 3 (3 points)}

Prove that for $n \ge 3$ a convex $n$-gon has $n(n-3)/2$ diagonals. (If it helps to draw
a picture, feel free to take a picture with your phone and submit it with your homework.)

\subsection*{Problem 4 (3 points)}

Recall that the Fibonacci numbers are defined recursively as follows:
\begin{align*}
  F_0 & = 0 \\
  F_1 & = 1 \\
  F_{n+2} & = F_{n+1} + F_n.
\end{align*}
Show $\sum_{i < n} F_i = F_{n+1} - 1$.

\subsection*{Problem 5 (3 points)}

Let $\alpha$ and $\beta$ be the two roots of $x^2 = x + 1$.
Show that for every $n$, $F_n = (\alpha^n - \beta^n) / \sqrt 5$.

\subsection*{Problem 6 (3 points)}

Remember the recursive definition of the greatest common divisor function:
\begin{align*}
\fn{gcd}(x, y) = \begin{cases}
  x & \text{if $y = 0$} \\
  \fn{gcd}(y, \fn{mod}(x, y)) & \text{otherwise}
\end{cases}
\end{align*}
Notice that the easiest way to show that the recursion is well founded is to notice that the
second argument decreases with each recursive call.

Show that for every nonnegative $x$ and $y$, there are integers $a$ and $b$ such that
$\fn{gcd}(x, y) = a x + b y$. You can use the fact that for nonzero $y$,
we have $x = \fn{div}(x, y) \cdot y + \fn{mod}(x, y)$, where $\fn{div}(x, y)$ denotes integer
division.


\end{document}