\documentclass[boldsans]{article}
\usepackage{ccfonts,fullpage,graphics,rotating,amsmath,amssymb}
\usepackage{hyperref}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\title{CSC236 Fall 2016\\Assignment \#1: induction\\
  {\bf due October 7th, 10 p.m.}}
\renewcommand{\today}{~}
\newcommand{\ul}{$\underline{~}$}
\newboolean{solutions}
\setboolean{solutions}{false}
\begin{document}
\maketitle\vspace{-2\baselineskip}
\noindent
The aim of this assignment is to give you some practice with various
forms of induction.  For each question below you will present a proof
by induction.  For full marks you will need to make it clear to the
reader that the base case(s) is/are verified, that the inductive step
follows for each element of the domain (typically the natural
numbers), where the inductive hypothesis is used and that it is used
in a valid case.

Your assignment must be typed to produce a PDF document
\textbf{a1.pdf} (hand-written submissions are not acceptable).  You
may work on the assignment in groups of 1, 2, or 3, and submit a
single assignment for the entire group on
\href{https://markus.cdf.toronto.edu/csc236-2016-09}{MarkUs}
\begin{enumerate}
\item Consider the Fibonacci-esque function $g$:
  \begin{equation*}
    g(n) =
    \begin{cases}
      1, & \text{if $n = 0$} \\
      3, & \text{if $n = 1$} \\
      g(n-2) + g(n-1) & \text{if }n> 1
    \end{cases}
  \end{equation*}
  Use complete induction to prove that if $n$ is a natural number
  greater than 1, then $2^{n/2} \leq g(n) \leq 2^n$.  You may
  \textbf{not} derive or use a closed-form for $g(n)$ in your proof.
\ifthenelse{\boolean{solutions}}{\input{fibonacci_solutions.tex}}{}

\item Suppose $B$ is a set of binary strings where each binary string is of length $n$. $n$
  is positive (greater than 0), and no two strings in $B$ differ in fewer
  than 2 positions.  Use simple induction to prove that $B$ has no more
  than $2^{n-1}$ elements.
\ifthenelse{\boolean{solutions}}{\input{binary_strings_solutions.tex}}{}

\item Define $T$ as the smallest set of strings such that:
  \begin{enumerate}
  \item $"b" \in T$
  \item If $t_1, t_2 \in T$, then $t_1 + "ene" + t_2 \in T$, where the
    $+$ operator is string concatenation.
  \end{enumerate}
  Use structural induction to prove that if $t\in T$ has $n$ "b"
  characters, then $t$ has $2n-2$ "e" characters.
  \ifthenelse{\boolean{solutions}}{\input{structural_solutions.tex}}{}

\item On
  \href{http://www.cs.toronto.edu/~vassos/b36-notes/notes.pdf}{page
    79} of the Course Notes the quantity $\phi = (1+\sqrt{5})/2$ is
  shown to be closely related to the Fibonacci function.  You may
  assume that $1.61803 < \phi < 1.61804$.  Complete the steps below to
  show that $\phi$ is irrational.
  \begin{enumerate}
  \item Show that $\phi(\phi -1) = 1$.
    \ifthenelse{\boolean{solutions}}{\input{phi_a.tex}}{}
  \item Rewrite the equation in the previous step so that you have
    $\phi$ on the  left-hand side, and on the right-hand side a
    fraction whose numerator and denominator are expressions that
    may only have integers, $+$ or $-$, and $\phi$.  There are two
    different fractions, corresponding to the two different factors in
    the original equation's left-hand side.  Keep both fractions
    around for future consideration.
    \ifthenelse{\boolean{solutions}}{\input{phi_b.tex}}{}
  \item Assume, for a moment, that there are natural numbers $m$ and
    $n$ such that $\phi=n/m$.  Re-write the right-hand side of both
    equations in the previous step so that you end up with fractions
    whose numerators and denominators are expressions that may only
    have integers, $+$ or $-$, $m$ and $n$.
    \ifthenelse{\boolean{solutions}}{\input{phi_c.tex}}{}
  \item Use your assumption from the previous part to construct a
    non-empty subset of the  natural numbers that contains $m$.  Use
    the Principle  of Well-Ordering, plus one of the two expressions
    for $\phi$ from the previous step to derive a contradiction.
    \ifthenelse{\boolean{solutions}}{\input{phi_d.tex}}{}
  \item Combine your assumption and contradiction from the  previous
    step into a proof that $\phi$ cannot be the ratio of  two natural
    numbers.  Extend this to a proof that $\phi$ is irrational.
    \ifthenelse{\boolean{solutions}}{\input{phi_e.tex}}{}
  \end{enumerate}

\item Consider the function $f$, where $3\div 2 = 1$ (integer
  division, like $3//2$ in Python):
  \begin{equation*}
    f(n) =
    \begin{cases}
      1 & \text{if }n=0 \\
      f^2(n\div 3) + 3f(n\div 3)&\text{if }n>0
    \end{cases}
  \end{equation*}
  Use complete induction to prove that for every natural number $n$
  greater than 2, $f(n)$ is a multiple of 7. \textbf{NB:} Think
  carefully about which natural numbers you are justified in using the
  inductive hypothesis for.
  \ifthenelse{\boolean{solutions}}{\input{base_cases_solutions.tex}}{}
\end{enumerate}
\end{document}
