\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}