% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 06 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about Sequences!
\problem\ [10pts] Consider the following sequence definitions. Write out the first 10 terms ($n \in \{0,\dots,9\}$) of each sequence.

\textbf{a.} [3pts] $a_0 = 2$ and $a_n = 2a_{n-1}-1$ for $n \geq 1$.

\[
\begin{array}[h]{r|cccccccccc}
n     & 0 & 1 & 2 & 3 &  4 &   5  &    6 &    7 &    8 & 9\\[1ex]
a_n & 2 & 3 & 5 & 9 & 17 & 35 & 69 & 137 & 273 & 545
\end{array}
\]

\textbf{b.} [3pts] $b_0 = 0$ and $b_n = b_{n-1} + \frac{1}{2^n}$ for $n \geq 1$.

\[
\begin{array}[h]{r|cccccccccc}
n     & 0 & 1 & 2 &3 & 4 & 5 & 6 & 7 & 8 & 9\\[1ex]
b_n & 0 & \frac{1}{2}& \frac{3}{4}& \frac{7}{8}& \frac{15}{16}& \frac{31}{32} & \frac{63}{64}& \frac{127}{128} & \frac{255}{256}& \frac{511}{512}
\end{array}
\]

\textbf{c.} [4pts] $c_0 = 1$, $c_1 = 2$, and $c_n = 2(c_{n-1} - c_{n-2})$ for $n \geq 2$.


\[
\begin{array}[h]{r|cccccccccc}
n     & 0 & 1 & 2 &3 & 4 & 5 & 6 & 7 & 8 & 9\\[1ex]
c_n & 1 & 2 & 2 & 0 & -4 & -8 & -8 & 0 & 16 & 32 
\end{array}
\]


% Problems about Sequences!
\clearpage
\problem\ [5pts] Let $\{d_n\}_{n=0}^\infty$ be a sequence with the recurrence relation $d_n = 2d_{n-1} - d_{n-2}$ for $n \geq 2$. (We do not specify the terms $d_0$, $d_1$.) Use backward reasoning to motivate the closed form $d_n = nd_1 - (n-1)d_0$.

We will apply the recurrence relation several times to deduce a pattern.

\begin{align*}
d_n &= 2d_{n-1} - d_{n-2}\\
&= 2(2d_{n-2}-d_{n-3})-d_{n-2}\\
&= (4-1)d_{n-2} - 2d_{n-3}\\
&= 3d_{n-2} -2d_{n-3}\\
&= 3(2d_{n-3}-d_{n-4})-2d_{n-3}\\
&= (6-2)d_{n-3}-3d_{n-4}\\
&= 4d_{n-3}-3d_{n-4}\\
&= 4(2d_{n-4}-d_{n-5})-3d_{n-4}\\
&= 5d_{n-4} - 4d_{n-5}\\
&\ \vdots\\
&= kd_{n-(k-1)}-(k-1)d_{n-k} &\text{For $k \geq 1$.}\\
&\ \vdots\\
&= nd_{n-(n-1)} - (n-1)d_{n-n} = nd_1 -(n-1)d_0.
\end{align*}


% Problems about Mathematical Induction!
 \clearpage
\problem\ [10pts] Mathematical induction can be used to prove things that can be proven directly. In the two problems below, you will essentially prove the induction step of an induction proof.

\textbf{a.} [5pts] For $n \geq 0$, let  $P(n)$ denote the sentence ``The $2 \times n$ chessboard can be tiled using dominoes.'' Prove ``$P(n) \implies P(n+1)$.''

\begin{proof}
Let $C$ be the $2 \times (n+1)$ chessboard.
Place a domino vertically on the far-right edge, leaving a $2 \times n$ chessboard of open squares.
Since the $2 \times n$ chessboard can be tiled using dominoes, that tiling can complete the tiling of $C$.
Therefore, the $2 \times (n+1)$ chessboard can be tiled using dominoes.
\end{proof}

\textbf{b.} [5pts] For $n \geq 0$, let  $Q(n)$ denote the sentence ``The $3 \times 2n$ chessboard can be tiled using dominoes.'' Prove ``$Q(n) \implies Q(n+1)$.''

\begin{proof}
Let $C$ be the $3 \times 2(n+1)$ chessboard.
Place two dominoes vertically in the top-right corner, one tile covering the positions $(1,2n+2), (2,2n+2)$ and the other covering positions $(1,2n+1), (2,2n+1)$.
Then place a domino horizontally in the bottom-right corner, covering the positions $(3,2n+2),(3,2n+1)$.
The remaining squares form a $3 \times 2n$ chessboard.
Since the $3 \times 2n$ chessboard can be tiled using dominoes, this tiling completes the tiling of $C$.
Therefore, the $3 \times 2(n+1)$ chessboard can be tiled using dominoes.
\end{proof}

% Problems about Mathematical Induction!
 \clearpage
\problem\ [10pts] Define a sequence $\{ f_n\}_{n=0}^\infty$ as $f_0 = 1$ and for $n \geq 1$, $f_n = \frac{1}{1+f_{n-1}}$.
Prove that for $n \geq 0$, $f_n = \frac{F_{n+1}}{F_{n+2}}$, where $\{F_n\}_{n=0}^\infty$ is the Fibonacci sequence.

\begin{proof}
We use induction.

Case $n = 0$: $f_0 = 1 = \frac{1}{1} = \frac{F_{1}}{F_2}$.

(Induction Hypothesis) Assume that $f_n = \frac{F_{n+1}}{F_{n+2}}$ for some $n \geq 0$.

Case $n+1$: Consider $f_{n+1}$.
\begin{align*}
f_{n+1} &= \frac{1}{1+f_n} &&\text{By recurrence relation of $f_{n+1}$}\\
	&= \frac{1}{1+\frac{F_{n+1}}{F_{n+2}}} &&\text{By Induction Hypothesis}\\
	&= \frac{1}{\frac{F_{n+1}+F_{n+2}}{F_{n+2}}} &&\\
	&= \frac{1}{\frac{F_{n+3}}{F_{n+2}}} &&\text{By recurrence relation $F_{n+3} = F_{n+2} + F_{n+1}$, since $n+3 \geq 2$.}\\
	&= \frac{F_{n+2}}{F_{n+3}}.
\end{align*}

Therefore, by induction we have that $f_n = \frac{F_{n+1}}{F_{n+2}}$ for all $n \geq 0$.
\end{proof}


% Problems about Mathematical Induction!
 \clearpage
\problem\ [10pts]  Let $\{A_n\}_{n=1}^\infty$ be an arbitrary sequence of non-empty sets.
Recall the \emph{$n$-fold Cartesian product} $\prod_{i=1}^n A_i$ is the set of $n$-tuples $(a_1,\dots,a_n)$ where each $a_i$ is an element in $A_i$.
The \emph{iterated  product} is the set sequence $\{B_n\}_{n=1}^\infty$ where $B_1 = A_1$, and for $n \geq 2$, $B_n = B_{n-1} \times A_n$. (Thus, $B_1 = A_1$, $B_2 = A_1 \times A_2$, $B_3 = (A_1 \times A_2) \times A_3$, etc.)
Use induction to prove that for all $n \geq 2$, there is a bijection $f_n$ from $n$-fold Cartesian product $\prod_{i=1}^n A_i$ to the iterated  product $B_n = B_{n-1} \times A_n$.
[Note: the $n$-fold Cartesian product $\prod_{i=1}^n A_i$ consists of $n$-tuples $(a_1,\dots,a_n)$, while the iterated product $B_n$ consists of ordered pairs $(b,a_n)$ where $b \in B_{n-1}$ and $a_n \in A_n$.]

\begin{proof}
We use induction on $n \geq 1$.

Case $n = 1$: Note that $A_1 = B_1$, so the \emph{identity map} $f_1 : A_1 \to B_1$ defined as $f_1(x) = x$ is a bijection between $A_1$ and $B_1$.

(Induction Hypothesis) Assume that for some $n \geq 1$ we have a bijection $f_n : \prod_{i=1}^n A_i \to B_n$.

Case $n+1$: 
Note that by the Induction Hypothesis there exists a bijection $f_n : \prod_{i=1}^n A_i \to B_n$.
We define a function $f_{n+1} : \prod_{i=1}^{n+1}A_i \to B_{n+1}$ as follows: For an arbitrary $(n+1)$-tuple $(x_1,\dots,x_n,x_{n+1})$ in $\prod_{i=1}^{n+1} A_i$, let $f_{n+1}(x_1,\dots,x_n,x_{n+1}) = (f_n(x_1,\dots,x_n), x_{n+1})$. 
We claim that $f_{n+1}$ is a bijection.
First, since $f_n(x_1,\dots,x_n) \in B_n$ for all $(x_1,\dots,x_n) \in \prod_{i=1}^n A_i$ (by Induction Hypothesis), we have that $(f_n(x_1,\dots,x_n), x_{n+1})$ is an element of $B_n \times A_{n+1}$ for every $(x_1,\dots,x_{n+1})\in \prod_{i=1}^{n+1} A_i$.
Therefore, $f_{n+1}$ is a well-defined function with codomain $B_{n+1} = B_n \times A_{n+1}$.

We claim $f_{n+1}$ is an injection:
Let $(x_1,\dots,x_n,x_{n+1})$ and $(y_1,\dots,y_n,y_{n+1})$ be elements of $\prod_{i=1}^{n+1} A_i$ where $f_{n+1}(x_1,\dots,x_{n+1}) = f_{n+1}(y_1,\dots,y_{n+1})$.
Since the first coordinate in these function outputs are equal, we have that $f_n(x_1,\dots,x_n) = f_n(y_1,\dots,y_n)$.
Since $f_n$ is an injection, we have that $(x_1,\dots,x_n) = (y_1,\dots,y_n)$.
Since the second coordinate in the function outputs are equal, $x_{n+1} = y_{n+1}$.
Therefore, $f_{n+1}$ is an injection.

We claim $f_{n+1}$ is a surjection:
Let $(y,z)\in B_n \times A_{n+1} = B_{n+1}$ be any element of the codomain.
Since $f_n$ is surjective, there exists an $n$-tuple $(x_1,\dots,x_n) \in \prod_{i=1}^n A_i$ where $f_n(x_1,\dots,x_n) = y$.
Since $z \in A_{n+1}$, note that $f_{n+1}(x_1,\dots,x_n,z) = (y,z)$ and therefore $(y,z)$ is in the range of $f_{n+1}$ and hence $f_{n+1}$ is surjective.

By induction, there exists a bijection $f_n : \prod_{i=1}^n A_i\to B_n$ for every $n \geq 1$.
\end{proof}


\end{document} 