\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=Sunday, November 07, 2021 17:37:54}
%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 220-002 Fall 2021 (Darij Grinberg): homework set 3}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 220-002 Fall 2021 (Darij Grinberg): homework set 3}

due date: Monday 2021-11-09 at noon on gradescope (
\url{https://www.gradescope.com/courses/313263} ).

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

This homework set is devoted to some further applications of induction
(including strong induction).

The first exercise is about matrix multiplication. For an introduction to
matrix multiplication, see any textbook on linear algebra (e.g.,
\cite[\S 10.1]{BoyVan18} goes over it in detail). However, all we need for
this exercise will be $2\times2$-matrices, so let us recall how matrix
multiplication works for them:

\begin{itemize}
\item The product $AX$ of two $2\times2$-matrices $A=\left(
\begin{array}
[c]{cc}%
a & b\\
c & d
\end{array}
\right)  $ and $X=\left(
\begin{array}
[c]{cc}%
x & y\\
z & w
\end{array}
\right)  $ is defined to be $\left(
\begin{array}
[c]{cc}%
ax+bz & ay+bw\\
cx+dz & cy+dw
\end{array}
\right)  $.

\item The $n$-th power $A^{n}$ of a $2\times2$-matrix $A$ is defined to be the
product $\underbrace{AA\cdots A}_{n\text{ factors}}$.
\end{itemize}

\begin{exercise}
\textbf{(a)} Prove that $\left(
\begin{array}
[c]{cc}%
1 & 1\\
0 & 1
\end{array}
\right)  ^{n}=\left(
\begin{array}
[c]{cc}%
1 & n\\
0 & 1
\end{array}
\right)  $ for each positive integer $n$. \medskip

\textbf{(b)} Find a formula for $\left(
\begin{array}
[c]{cc}%
a & b\\
0 & c
\end{array}
\right)  ^{n}$ (with $a,b,c$ being real numbers and $n$ being a positive integer).
\end{exercise}

The next two exercises rely on binomial coefficients. Recall that if $n$ is
any real number and $k\in\mathbb{N}$, then the binomial coefficient
$\dbinom{n}{k}$ is defined by%
\[
\dbinom{n}{k}:=\dfrac{n\left(  n-1\right)  \left(  n-2\right)  \cdots\left(
n-k+1\right)  }{k!}.
\]
When $k=0$, this equals $1$, because both numerator and denominator are empty
products. Do \textbf{not} use the formula $\dbinom{n}{k}=\dfrac{n!}{k!\left(
n-k\right)  !}$ unless you are sure that its conditions ($n\in\mathbb{N}$ and
$0\leq k\leq n$) are satisfied!

\begin{exercise}
Prove that every $n\in\mathbb{N}$ and $a\in\mathbb{R}$ satisfy%
\[
\sum_{k=0}^{n}\dbinom{k+a}{k}=\dbinom{n+a+1}{n}.
\]


(For example, for $n=4$ and $a=2$, this is saying that
\[
\dbinom{2}{0}+\dbinom{3}{1}+\dbinom{4}{2}+\dbinom{5}{3}+\dbinom{6}{4}%
=\dbinom{7}{4}.
\]
Keep in mind that $a$ doesn't have to be an integer in general!)
\end{exercise}

\begin{exercise}
Let $n\in\mathbb{N}$. Prove that%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dbinom{n}{k}=%
\begin{cases}
0, & \text{if }n\neq0;\\
1, & \text{if }n=0.
\end{cases}
\]
(For example, for $n=4$, this is saying that $\dbinom{4}{0}-\dbinom{4}%
{1}+\dbinom{4}{2}-\dbinom{4}{3}+\dbinom{4}{4}=0$.)
\end{exercise}

\begin{exercise}
Find the error(s) in the following fake proof:

We claim that $3^{n}=1$ for each $n\in\mathbb{N}$.

\textit{Proof:} We proceed by strong induction on $n$. So we let
$n\in\mathbb{N}$ be arbitrary, and we assume (as the induction hypothesis)
that $3^{k}=1$ for each $k<n$. We must now prove that $3^{n}=1$.

By our induction hypothesis, we have $3^{n-1}=1$ (since $n-1<n$) and
$3^{n-2}=1$ (since $n-2<n$). Now, $3^{n}=\dfrac{\left(  3^{n-1}\right)  ^{2}%
}{3^{n-2}}$ (since the laws of exponents yield $\dfrac{\left(  3^{n-1}\right)
^{2}}{3^{n-2}}=3^{2\cdot\left(  n-1\right)  -\left(  n-2\right)  }=3^{n}$). In
view of $3^{n-1}=1$ and $3^{n-2}=1$, this rewrites as $3^{n}=\dfrac{1^{2}}%
{1}=1$. This completes the induction step, and thus the claim is proved.
\end{exercise}

\begin{exercise}
\label{exe.laurent.t}Define a sequence $\left(  t_{0},t_{1},t_{2}%
,\ldots\right)  $ of positive rational numbers recursively by setting%
\begin{align*}
t_{0}  &  =1,\ \ \ \ \ \ \ \ \ \ t_{1}=1,\ \ \ \ \ \ \ \ \ \ t_{2}%
=1,\ \ \ \ \ \ \ \ \ \ \text{and}\\
t_{n}  &  =\dfrac{1+t_{n-1}t_{n-2}}{t_{n-3}}\ \ \ \ \ \ \ \ \ \ \text{for each
}n\geq3.
\end{align*}
(So its next entries after $t_{2}$ are%
\begin{align*}
t_{3}  &  =\dfrac{1+t_{2}t_{1}}{t_{0}}=\dfrac{1+1\cdot1}{1}=2;\\
t_{4}  &  =\dfrac{1+t_{3}t_{2}}{t_{1}}=\dfrac{1+2\cdot1}{1}=3;\\
t_{5}  &  =\dfrac{1+t_{4}t_{3}}{t_{2}}=\dfrac{1+3\cdot2}{1}=7;\\
t_{6}  &  =\dfrac{1+t_{5}t_{4}}{t_{3}}=\dfrac{1+7\cdot3}{2}=11,
\end{align*}
and so on.) \medskip

\textbf{(a)} Prove that $t_{n+2}=4t_{n}-t_{n-2}$ for each $n\geq2$. \medskip

\textbf{(b)} Prove that $t_{n}$ is a positive integer for each integer
$n\geq0$. \medskip

[\textbf{Hint:} Use regular induction for part \textbf{(a)} and strong
induction for part \textbf{(b)}. Note that the \textquotedblleft
positive\textquotedblright\ part is clear from the definition, so you only
need to prove the \textquotedblleft integer\textquotedblright\ part in
\textbf{(b)}.]
\end{exercise}

\begin{exercise}
Let $m\in\mathbb{N}$. Prove that there exists a way to arrange the first $m$
positive integers ($1,2,\ldots,m$) in a row in such a way that the average of
two numbers never stands between these two numbers.

(For example, for $m=8$, one such arrangement is $1,5,3,7,2,6,4,8$. The
arrangement $1,3,2,7,8,5,6,4$ is invalid because the average of $1$ and $5$ is
$3$, which stands between $1$ and $5$.) \medskip

[\textbf{Hint:} First show that there is such an arrangement when $m$ is a
power of $2$ (that is, when $m=2^{n}$ for some $n\in\mathbb{N}$). Then, choose
a sufficiently large power of $2$ and remove all entries larger than $m$.]
\end{exercise}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[BoyVan18]{BoyVan18}Stephen Boyd, Lieven Vandenberghe,
\textit{Introduction to Applied Linear Algebra: Vectors, Matrices, and Least
Squares}, Cambridge University Press 2018.\newline\url{https://web.stanford.edu/~boyd/vmls/vmls.pdf}
\end{thebibliography}


\end{document}