\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, February 03, 2023 00:27:00}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 221 Winter 2023 (Darij Grinberg): midterm 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 221 Winter 2023 (Darij Grinberg): midterm 1}

due date: Sunday 2023-02-14 at 11:59PM on gradescope (
\url{https://www.gradescope.com/courses/487830} ).

Please solve only \textbf{4 of the 6 exercises}.

\textbf{NO collaboration allowed -- this is a midterm!}

(But you can still ask me questions.)
\end{center}

Recall that $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $.

\begin{exercise}
Let $n\in\mathbb{N}$, and let $q$ be any number distinct from $1$. Prove that%
\[
\sum_{k=1}^{n}kq^{k}=q\cdot\dfrac{nq^{n+1}-\left(  n+1\right)  q^{n}%
+1}{\left(  q-1\right)  ^{2}}.
\]

\end{exercise}

\begin{exercise}
Let $\left(  a_{0},a_{1},a_{2},\ldots\right)  $ be a sequence of integers
defined recursively by%
\begin{align*}
a_{0}  &  =2,\ \ \ \ \ \ \ \ \ \ a_{1}=1,\\
a_{n}  &  =a_{n-1}+6a_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq2.
\end{align*}
Prove that $a_{n}=3^{n}+\left(  -2\right)  ^{n}$ for each $n\in\mathbb{N}$.
\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Prove that%
\[
\underbrace{1+2+\cdots+n}_{=\sum_{k=1}^{n}k}=\underbrace{n^{2}-\left(
n-1\right)  ^{2}+\left(  n-2\right)  ^{2}-\left(  n-3\right)  ^{2}\pm
\cdots+\left(  -1\right)  ^{n-1}1^{2}}_{=\sum_{k=1}^{n}\left(  -1\right)
^{n-k}k^{2}}.
\]

\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Prove that%
\[
\prod_{i=0}^{n}\dbinom{2i}{i}=2^{n}\prod_{i=0}^{n}\dbinom{n+i}{n-i}.
\]

\end{exercise}

\begin{exercise}
Let $\left(  a_{0},a_{1},a_{2},\ldots\right)  $ be a sequence of integers
defined recursively by%
\[
a_{n}=1+a_{0}a_{1}\cdots a_{n-1}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq0.
\]
(In particular, $a_{0}=1+\underbrace{a_{0}a_{1}\cdots a_{0-1}}_{=\left(
\text{empty product}\right)  =1}=1+1=2$.) Here are the first few entries of
this sequence:%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|}\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$\\\hline
$a_{n}$ & $2$ & $3$ & $7$ & $43$ & $1807$ & $3263443$ & $10650056950807$%
\\\hline
\end{tabular}
\]
(notice the astronomical growth!).

\textbf{(a)} Prove that%
\[
a_{n+1}=a_{n}^{2}-a_{n}+1\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq0.
\]


\textbf{(b)} Prove that
\[
\dfrac{1}{a_{0}}+\dfrac{1}{a_{1}}+\cdots+\dfrac{1}{a_{n-1}}=1-\dfrac{1}%
{a_{n}-1}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq0.
\]

\end{exercise}

\begin{noncompile}
\textbf{(c)} Prove that $\gcd\left(  a_{n},a_{m}\right)  =1$ for any distinct
$n,m\in\mathbb{N}$.

\textbf{(d)} Use this to prove that there are $\infty$ many primes.

\textbf{(e)} Show that $1+a_{n}^{2}\mid1+a_{n+1}^{2}$ for all $n\in\mathbb{N}$.
\end{noncompile}

\bigskip

Now, recall the Tower of Hanoi puzzle (as discussed in Lecture 1), and let
$m_{n}$ denote the \# of moves needed to win (= solve this puzzle) with $n$
disks. As we have seen in Theorem 1.2.2 (Lecture 2), we have $m_{n}=2^{n}-1$
for each $n\in\mathbb{N}$.

Consider the variant of the Tower of Hanoi puzzle in which we have $4$ instead
of $3$ pegs, but otherwise the rules of the game are the same (and the goal is
still is to move all $n$ disks from peg $1$ to peg $3$). Let $t_{n}$ denote
the \# of moves needed to win this variant with $n$ disks.

\begin{exercise}
\textbf{(a)} Prove that
\[
t_{a+b}\leq m_{b}+2t_{a}\ \ \ \ \ \ \ \ \ \ \text{for any }a,b\in\mathbb{N}.
\]


\textbf{(b)} Prove that $t_{4}\leq9$.
\end{exercise}


\end{document}