\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=Monday, January 16, 2023 16:50:38}
%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 2}
\ohead{page \thepage}
\cfoot{}
\begin{document}

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

due date: Wednesday 2021-10-27 at noon on gradescope (
\url{https://www.gradescope.com/courses/313263} ).

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

\begin{exercise}
Complete the proof of the triangle inequality for reals (\textquotedblleft For
any real numbers $x$ and $y$, we have $\left\vert x\right\vert +\left\vert
y\right\vert \geq\left\vert x+y\right\vert $\textquotedblright) that we
started in Lecture 11.
\end{exercise}

For each $n\in\mathbb{N}$, we define $n!$ (this is called the \emph{factorial}
of $n$, and is pronounced \textquotedblleft$n$ factorial\textquotedblright) to
be the \textbf{product} of the first $n$ positive integers. That is, we set%
\[
n!=1\cdot2\cdot\cdots\cdot n.
\]
Here (and everywhere else), we follow the convention that an empty product
(i.e., a product with no factors) is $1$ by definition. Thus, $0!=1$ (being
such an empty product). Here is a little table of factorials:%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|c|}\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\\hline
$n!$ & $1$ & $1$ & $2$ & $6$ & $24$ & $120$ & $720$ & $5\ 040$ &
$40\ 320$\\\hline
\end{tabular}
\ \ .
\]
It is clear that $n!=\left(  n-1\right)  !\cdot n$ for each positive integer
$n$ (because $n!$ is the product $1\cdot2\cdot\cdots\cdot n$, whereas $\left(
n-1\right)  !$ is the product $1\cdot2\cdot\cdots\cdot\left(  n-1\right)  $,
which is the previous product without its last factor).

\begin{exercise}
\textbf{(a)} Prove that
\[
1+3+5+\cdots+\left(  2n-1\right)  =n^{2}%
\]
for each $n\in\mathbb{N}$. (The left hand side here is the sum of the first
$n$ \textbf{odd} positive integers.) \medskip

\textbf{(b)} Prove that%
\[
1\cdot1!+2\cdot2!+3\cdot3!+\cdots+n\cdot n!=\left(  n+1\right)  !-1
\]
for each $n\in\mathbb{N}$.
\end{exercise}

(Meanwhile, there is no such simple formula for $1!+2!+3!+\cdots+n!$. Not
every sum simplifies!)

\begin{exercise}
Let $q$ and $d$ be two real numbers such that $q\neq1$. Let $\left(
a_{0},a_{1},a_{2},\ldots\right)  $ be a sequence of real numbers. Assume that%
\begin{equation}
a_{n+1}=qa_{n}+d\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\mathbb{N}.
\label{eq.prop.ind.ari-geo.ass}%
\end{equation}
Prove that%
\begin{equation}
a_{n}=q^{n}a_{0}+\dfrac{q^{n}-1}{q-1}d\ \ \ \ \ \ \ \ \ \ \text{for each }%
n\in\mathbb{N}. \label{eq.prop.ind.ari-geo.claim}%
\end{equation}

\end{exercise}

Now, we recall again the Fibonacci sequence $\left(  f_{0},f_{1},f_{2}%
,\ldots\right)  $ that we got to know in Lecture 12. Recall that it is defined
recursively by $f_{0}=0$ and $f_{1}=1$ and $f_{n}=f_{n-1}+f_{n-2}$ for each
$n\geq2$.

\begin{exercise}
\textbf{(a)} Show that
\[
f_{n+1}f_{n-1}-f_{n}^{2}=\left(  -1\right)  ^{n}\ \ \ \ \ \ \ \ \ \ \text{for
every positive integer }n.
\]
(The word \textquotedblleft Show\textquotedblright\ is a synonym for
\textquotedblleft Prove\textquotedblright.)

\textbf{(b)} Show that
\[
f_{1}^{2}+f_{2}^{2}+\cdots+f_{n}^{2}=f_{n}f_{n+1}\ \ \ \ \ \ \ \ \ \ \text{for
each }n\in\mathbb{N}.
\]
(The left hand side here is the sum of the squares of the first $n$ positive
Fibonacci numbers.)
\end{exercise}

Let us now generalize the properties of the Fibonacci sequence that we started
proving in Lecture 12:

\begin{exercise}
Let $u$ and $v$ be two real numbers. Let $\left(  x_{0},x_{1},x_{2}%
,\ldots\right)  $ be a sequence of real numbers such that $x_{0}=0$ and
$x_{1}=1$ and%
\[
x_{n}=ux_{n-1}+vx_{n-2}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq2.
\]
(When $u=1$ and $v=1$, this is the Fibonacci sequence.) Prove that%
\[
x_{n+m+1}=vx_{n}x_{m}+x_{n+1}x_{m+1}\ \ \ \ \ \ \ \ \ \ \text{for all }%
n,m\in\mathbb{N}.
\]

\end{exercise}

Now, let us extend the Fibonacci sequence $\left(  f_{0},f_{1},f_{2}%
,\ldots\right)  $ \textquotedblleft to the left\textquotedblright\ by defining
$f_{n}$ not only for nonnegative integers $n$, but also for negative integers
$n$. To do so, we simply rewrite the equation $f_{n}=f_{n-1}+f_{n-2}$ (which
we used to recursively define the Fibonacci sequence) as $f_{n-2}%
=f_{n}-f_{n-1}$. This allows us to compute $f_{n-2}$ from $f_{n}$ and
$f_{n-1}$. Thus, we can compute $f_{-1}$ from $f_{1}$ and $f_{0}$, then
compute $f_{-2}$ from $f_{0}$ and $f_{-1}$, and so on:%
\begin{align*}
f_{-1} &  =f_{1}-f_{0}=1-0=1;\\
f_{-2} &  =f_{0}-f_{-1}=0-1=-1;\\
f_{-3} &  =f_{-1}-f_{-2}=1-\left(  -1\right)  =2;\\
f_{-4} &  =f_{-2}-f_{-3}=\left(  -1\right)  -2=-3;\\
&  \ldots.
\end{align*}
Thus, we gradually extend the Fibonacci sequence to the left, obtaining a
\textquotedblleft two-sided sequence\textquotedblright\ $\left(  \ldots
,f_{-2},f_{-1},f_{0},f_{1},f_{2},\ldots\right)  $ that is \textquotedblleft
infinite in both directions\textquotedblright. By virtue of its construction,
it satisfies $f_{n}=f_{n-1}+f_{n-2}$ not only for all $n\geq2$, but also for
all integers $n$. However, a quick look at the first (say) $7$ negative
Fibonacci numbers reveals that they are not as new as they might seem: They
are just copies of the positive Fibonacci numbers with signs. More precisely,
it looks like we have%
\begin{equation}
f_{-n}=\left(  -1\right)  ^{n-1}f_{n}\ \ \ \ \ \ \ \ \ \ \text{for each }%
n\in\mathbb{N}.\label{eq.fib.neg.f-n=}%
\end{equation}


\begin{exercise}
\label{exe.ind.fib.neg.f-n=}\textbf{(a)} Try to prove (\ref{eq.fib.neg.f-n=})
directly by induction on $n$. (So the induction step involves assuming that
$f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ and proving that $f_{-\left(
n+1\right)  }=\left(  -1\right)  ^{n}f_{n+1}$.) Does this work? \medskip

\textbf{(b)} Now, instead, try to prove the \textbf{stronger} claim that
\textquotedblleft$f_{-n}=\left(  -1\right)  ^{n-1}f_{n}$ and $f_{-n+1}=\left(
-1\right)  ^{n-2}f_{n-1}$ for each $n\in\mathbb{N}$\textquotedblright\ by
induction on $n$. Does this work?
\end{exercise}


\end{document}