
\documentclass[10pt]{article}
\usepackage{amsmath,amssymb,amsfonts,fancyhdr}
\usepackage{graphicx}
%
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.2in}
\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}
%\usepackage{fullpage}
\renewcommand{\headrulewidth}{1pt}
\setlength{\headsep}{1cm}
% \usepackage{txfonts}
\usepackage{newcent}
\usepackage{fancyhdr}
\usepackage{multirow}   % for table formatting
\usepackage{hyperref}  % for weblinks in pdf
\usepackage{color}


\newcommand{\ds}{\displaystyle} 
\newcommand{\QQ}{{\mathbb{Q}}} % blackboard Q
\newcommand{\Qbar}{{\overline{\QQ}}} % blackboard Qbar
\newcommand{\ZZ}{{\mathbb{Z}}} % blackboard Z
\newcommand{\NN}{{\mathbb{N}}} % blackboard N
\newcommand{\CC}{{\mathbb{C}}} % blackboard C
\newcommand{\Zplus}{{\mathbb{Z^+}}} % blackboard Z^+
\newcommand{\FF}{{\mathbb{F}}} % blackboard F
\newcommand{\RR}{{\mathbb R}} % blackboard R
\newcommand{\Rtwo}{{\mathbb R^2}} % blackboard R^2
\newcommand{\Rthree}{{\mathbb R^3}} % blackboard R^3
\newcommand{\RRn}{{\mathbb R^n}} % blackboard R^n
\newcommand{\D}{{\cdot}} % dot
\def\mod#1{{\ifmmode\text{\rm\ (mod~$#1$)}
\else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}}

\def\tra{70}   %text rotation angle in table header
\newcommand{\tablehead}[1]{\rotatebox{\tra}{\scriptsize{#1}}}


%----------- colours ------------------------------------------------------
\definecolor{SFUred}{rgb}{0.60547,0.140625,0.17969}
\definecolor{SFUblue}{rgb}{.1602, .2734, .51172}
\definecolor{SFUgrey}{rgb}{.28515,.28125,.25}

\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%------------------------------------------------------------------------------
%amps stuff

\usepackage{enumitem}
\setlist[enumerate,1]{label=}
\setlist[enumerate,2]{label=\Alph*.}
\setlist[enumerate,3]{label=\arabic*.}
\setlist[enumerate,4]{label=(\alph*)}



% check boxes for after instructors questions
\newcommand{\insertcheckboxes}{
\begin{center}
\fbox{
\begin{tabular}{ccccc}
done & checked & corrected & study MT & study final \\
$\Box$ &  $\Box$ &  $\Box$ &  $\Box$ &  $\Box$
\end{tabular}
}
\end{center}
}


% standard basis vectors
\def\ihat{{\bf \hat{i}}}
\def\jhat{{\bf \hat{j}}}
\def\khat{{\bf \hat{k}}}

% vector arrow notation
\newcommand{\bvec}[1]{\vec{ \bf #1}}  % absolute value


\newcommand{\twovec}[2]{\left[\begin{array}{c}
#1\\ #2\\ \end{array}\right] }

\newcommand{\closethegap}{\vspace{-2mm} }

\newcommand{\threevec}[3]{\left[\begin{array}{c}
#1\\ #2\\ #3\\ \end{array}\right] }

\newenvironment{soln}[1]{ \textit{Solution #1:} }{\medskip}

\pagestyle{plain}

%------------------------------------------------
% different types of labels for lists
% 1) type of label
%\renewcommand{\theenumi}{\arabic{enumi}}   default
%\renewcommand{\theenumi}{\alph{enumi}}     alphabetic   (use capital A for capitals)
%\renewcommand{\theenumi}{\roman{enumi}}    roman numerals (use capital R for capitals)
%
% 2) formatting of label
%\renewcommand{\labelenumi}{(\theenumi)}   default
%\renewcommand{\labelenumi}{\theenumi.}    remove brackets
%------------------------------------------------


%------------ Course Information --------------------
\newcommand{\coursename}{Discrete Mathematics II}
\newcommand{\coursenum}{MACM 201 - D100, D200 and D300}
\newcommand{\semester}{Fall 2020}
\newcommand{\instructor}{Michael Monagan,Amarpreet Rattan,Mahsa Faizrahnemoon}

%------------ Assignment Information -------------
\newcommand{\anum}{3}
\newcommand{\duedate}{Monday February 8, 2021}
\newcommand{\duetime}{11:00 pm}

\pagestyle{fancy}
\fancyhf{} 

\lhead{\includegraphics[height=1cm]{logo.png}}
\rhead{\large\sc \coursenum ~~~~Assignment\ \#\anum}
\lfoot{ {\color{blue} \sc Copyright  \instructor}}
\rfoot{{\small \thepage}}



%--------- Now for the document ----------------------------------

\begin{document}
\hfill{{\bf Due Date}:     \duedate, \duetime}

\subsection*{Instructions}
Answer all questions on paper or a tablet using your own handwriting.
Please number each page.
Include a cover page with your name, student ID number and a list of
the questions you answered.
If you use paper make a photo of each page and upload your solutions to crowdmark.
If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.

\begin{enumerate}
\item { \color{SFUred} \textbf{Textbook Reading} }  

		\begin{itemize}	
			\item Section: 3.7 -- we will not cover variance 
			\item Sections: 10.1
                 \end{itemize}


%=====================================
% Definitions, Concepts & Keywords
%=====================================
\item {\color{SFUred}\textbf{Definitions, Concepts \& Keywords}}
%\textbf{Definitions, Concepts \& Keywords}:

   \begin{itemize}
   \item[$\bullet$] Random variables, expected value
   \item[$\bullet$] The bins and balls problem and the coupon collectors problem
   \item[$\bullet$] Construct and solve first order recurrence relations
   
   \end{itemize}

\item {\color{SFUred}\textbf{Exercises}}

   \begin{enumerate}

   %=====================================
   % Textbook Questions
   %=====================================	
   \item  \textbf{Textbook Questions} 

        \begin{itemize}
        \item[]  Section 3.7 Exercise 2.
	\item[]  Section 10.1 Exercises 1, 2. % 3, 6
        
        \end{itemize}

   \item \textbf{Instructors Questions}

   \begin{enumerate}


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %
    %  Probability
    %
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   \item Suppose John tosses a coin 5 times.  Let $X$ be the number of heads.
         \begin{itemize}
         \item[(a)] Calculate $Pr(X=x)$ for $x \in \{0,1,2,3,4,5\}$ and find $E(X)$.
         % C(5,k)/2^k = 1/32, 5/32, 10/32, 10/32, 5/32, 1/32
         % E[X] = (0*1+1*5+2*10+3*10+4*5+5*1)/32 = 80/32 = 2.5
         \item[(b)] If $Y$ is the number of tails, what is $E(Y)$?
         \end{itemize}

   \item Let $X$ be a random variable with $r(X) = \{1,2,3,4\}$
         and \ $\Pr(X=x) = c/x$ \ for some constant $c$.
         \begin{itemize}
         \item[(a)] Determine $c$.
         \item[(b)] Calculate $\Pr(X=x)$ for $x \in \{1,2,3,4\}$ and find $E(X)$.
         \end{itemize}

    \item In a card game each player writes down 4 distinct cards from
        a standard deck of 52 cards.  The dealer draws one card at random from the deck.
        The player wins if they chose that card.
        \begin{itemize}
          \item[(a)] What is the expected number of times the player must 
                     play the game to win the game?
                     % p = 4/52 = 1/13, E[T] = 1/p = 13.
    
          \item[(b)] If the player must pay 1 dollar to play the game and gets 10
                     dollars if they win the game, what is the expected winnings if 
                     the player plays the game 20 times.
                     % 1/13 x $10 x 20 - 12/13 x $1 x 20 = -$3.08.
          \end{itemize}

   %\item  For any probability distibution, the sum of the probabilities must be 1.
   %       Let $T$ be geometrically distributed with parameter $p$.
   %       In class we showed that
   %       $$\Pr(T = k) = p(1-p)^{k-1} ~~\text{for}~ k \ge 1$$
   %       and $E(T)=1/p$.  Show that the probabilities sum to 1.
   %       % Solution - Maple sum syntax 😊
   %       % sum( Pr(T=k), k=r(T) ) = sum( p(1-p)^(k-1), k=1..infinity )
   %       % = p sum( q^(k-1), k=1..infinity ) where q=1-p
   %       % = p sum( q^k, k=0..infinity ) = p/(1-q) = p/p = 1

   \item If $X$ be binomially distributed with parameters $p$ and $n$ then
         $$ \Pr(X=k) = {n \choose k} p^k (1-p)^{n-k} ~~{\rm for}~ 0 \le k \le n.$$
         Show that the probabilities add to 1, that is, show that
         $$\sum_{k=0}^n {n \choose k} p^k (1-p)^{n-k} = 1.$$
         Hint: it's easy if you use the binomial theorem!
         
   \item Suppose we toss a coin 4 times.  Let $p$ be the probability of getting heads.
         Calculate the probability of getting 3 heads for $p=1/2$ and $p=2/3$.

   \item \begin{itemize}
         \item[(a)] Let $X$ be a random variable and $a$ be a constant.
                    Show that $E(aX) = a E(X).$ \\
                    Follow the proof that $E(X+Y)=E(X)+E(Y)$ given in class.
         % E(aX) = sum( (aX)(s) Pr(s), s in S ) = sum( aX(s) Pr(s), s in S ) 
         %       = a sum( X(s) Pr(s), s in S ) = a E(X)
         \item[(b)] Let $X$ and $Y$ be two random variables.
                    Suppose we know $E(X)=7$ and $E(Y)=3$. \\
                    Let $Z=X-Y$ be a random variable.
                    What is $E(Z)$?  Justify your answer.
                    % E(Z) = E(X-Y) = E(X+(-Y)) = E(X)+E(-Y)
                    %      = E(X)+(-1) E(Y) E(X)-E(Y) = 7-3 = 4.
         \end{itemize}

    % Lecture 10 on bins and balls and the coupon collectors problem
   \item Suppose we toss 3 balls into 3 bins randomly.
         Let $X$ be the number of balls in a bin.
         \begin{itemize}
         \item[(a)] Determine $\Pr(X=x)$ for $x = 0,1,2,3.$
         \item[(b)] Calculate $E(X)$.  You should get 1.
         \end{itemize}
         % > E := (m,n,k) -> binomial(m,k)*(1/n)^k*(1-1/n)^(m-k);
         % > seq( E(3,3,x), x=0..3 );
         %                             8/27, 4/9, 2/9, 1/27
         % > evalf(%%,5);
         %                     0.29630, 0.44444, 0.22222, 0.037037
         % > add( x*E(3,3,x), x=0..3 );
         %                                       1

   %\item Suppose we toss $m$ balls into $n$ bins randomly. \\
   %      Let $X$ be the expected number of empty bins. \\
   %      In class we showed that $E(X) = n (1-1/n)^m$.
   %      For $n=10$ and $m=5,10,20$ calculate $E(X)$. \\
   %      For the case $n=10$ and $m=20$, interpret the result for $E(X)$
   %      (write one sentence in English to explain what the result means).

   \item Suppose we toss $m$ balls into $n$ bins randomly.
         Let $X$ be the number of bins with exactly {\bf one} ball in them.
         Determine a formula for the probability $p$ that a bin has one ball in it
         and then calculate $E(X)$, the expected number of bins with one ball.
         For $m=n=10$ calculate $p$ and $E(X)$.  You should get $p=0.38742$.

   \item Every summer David and Jennifer take a vacation at a resort in Florida.
         The resort gives each guest a free dinner at one of the 5 local restaurants.
         If the restaurant is chosen by the resort at random,
         how many times, on average, must David and Jennifer stay at the resort before they
         get a free dinner at all 5 restaurants ?

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %
    %  Recurrences
    %
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item Consider the recurrence $a_{n+1} = 3 a_n - a_{n-1}$ with $a_1 = 1$, $a_2 = 1$.
          \begin{itemize}
          \item[(a)] Calculate $a_0,a_3,a_4$.
           % a3 = 3a2-a1 = 3-1=2
           % a4 = 3a3-a2 = 6-1=5
           % a5 = 3a4-a3 = 15-2=13
           % a2 = 3a1-a0 => a0 = 3a1-a2 = 3-2=2.
          \item[(b)] Is this recurrence a first order recurrence or second order?
          \item[(b)] Is this recurrence homogeneous or non-homogeneous?
          \end{itemize}

  \item Below is C code, and Python code, for a crazy function.
        The input is an array $A$ of $n$ integers.

\bigskip

\begin{minipage}[t]{8cm}
 C code:
\begin{verbatim}
 1: int crazy( int A[], int n ) {
 2:      int i,s;
 3:      if( n<=1 ) return A[0];
 4:      for( i=1; i<n; i++ )
 5:          A[i-1] += A[i];
 6:      s = crazy(A,n-1);
 7:      return s;
 8: }
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{6cm}
 python code:
\begin{verbatim}
 1:  def crazy(A,n):
 2:      if n<=1:
 3:          return A[0]
 4:      for i in range(1,n):
 5:          A[i-1] += A[i]
 6:      s = crazy(A,n-1)
 7:      return s
\end{verbatim}
\end{minipage}

\bigskip

    To estimate how long crazy function takes to execute as a function of $n$,
    we will count the number of times line 5 is executed.
    Let $c_n$ be the number of times line 5 is executed.
   \begin{itemize} 
    \item[(a)] Give a recurrence equation and an initial value for $c_n$.
    \item[(b)] Solve the recurrence for $c_n$ and determine $c_{10}$ and $c_{100}$.
   \end{itemize}

   \item  As I write this the number of people in Canada currently 
          with COVID is 56 thousand.
          Government officials are very worried about the new strain of the virus 
          from the UK because it is estimated to be
          1.4 times more contagious than the dominant strain in Canada.
          Suppose it takes hold in Canada and the number of people with COVID
          increases by a factor of 1.2 every week.

          \begin{itemize}
          \item[(a)]
          Let $i_n$ be the number of people with COVID after $n$ weeks.
          Give a recurrence relation for $i_n$ and   
          solve the recurrence using $i_0=56$ thousand.
          \item[(b)]
          How many weeks will it take before the number of people with COVID
          increases by a factor of 10 to 560 thousand active cases?
          \end{itemize}

  \item Solve the following recurrences for the given initial values

       \begin{itemize}
         \item[(a)]  $a_n=a_{n-1}+2n $ for $n>1$ and $a_1=1$.
         \item[(b)]  $a_n=a_{n-1}+(n-1)^2$ for $n>1$ and $a_1=0$.
       \end{itemize}

  %\item  Consider the recurrence relations and possible solutions.
  %       \begin{itemize}
  %       \item[(a)] $a_n = 2 a_{n-1} + 1$  and
  %       \item[(b)] $a_n - 3 a_{n-1} + 2 a_{n-2} = 0$.
  %       \end{itemize}
  %       \begin{itemize}
  %       \item[(1)] $a_n = 2^n+1$
  %       \item[(2)] $a_n = 2^n-1$
  %       \item[(3)] $a_n = 2^{n+1}-1$
  %       \end{itemize}
  %       Match the solutions with the recurrence relations.
         
  
\item The first few $pentagonal$ $ numbers$ are 1, 5, 12, and 22 as shown
      in the figure below.

      \includegraphics[height=2.5cm]{Pentagonal.png}

      \medskip
      Find and solve a recurrence relation for the $n$th pentagonal number.

   \item Consider $P_n$ the path graph on $n$ vertices.
         Suppose vertices can be coloured red, green or blue.
         Let $c_n$ be the number of ways the vertices in $P_n$ can be coloured 
         such that no two adjacent vertices are coloured blue. 

           \begin{itemize}
           \item[(a)] How many colourings are there for $P_1$, $P_2$, and $P_3$.
           \item[(b)] Find a (second order) recurrence for $c_n$.
           \item[(c)] Using the recurrence calculate $c_3$, $c_4$ and $c_5$.
           \end{itemize}

   

%
%=======================================================
%=======================================================
%=========                              ================
%=========  Selected Hints and Answers  ================
%=========                              ================
%=======================================================
%=======================================================
\end{enumerate}
\end{enumerate}

%\item {\color{SFUred}\textbf{ Selected Hints \& Answers}}
%
%Some final answers are given below. This is to provide you instant feedback on the validity of your solution - i.e. a quick check if your line of reasoning is correct. A complete solution requires full justification as to why these are the answers. 

\end{enumerate}
\end{document}
