% 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 --- INSERT NAME HERE}

\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$.

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

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


% Problems about Sequences!
\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$.


% 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)$.''

\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)$.''


% 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.


% 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$.]




\end{document} 