\documentclass[10pt]{article}
\usepackage[margin=0.7in,top=0.5in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumitem}
\usepackage{ulem}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\operatorname{Var}}
\renewcommand{\P}{\mathbb{P}}
\newpagestyle{main}[\small]{
\headrule
\sethead[\usepage][][]
{}{}{\usepage}
}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\pagenumbering{gobble}
\title{\sc Math 60 -- Homework 2}
\author{due Wednesday, April 11}
\date{}
\begin{document}
\maketitle
\pagestyle{main}
\textbf{Instructions:} This assignment is due at the \emph{beginning} of class. Staple your work together (do not just fold over the corner). Please write the questions in the correct order. If I cannot read your handwriting, you won't receive full credit.\\
%\emph{You may use Wolfram Alpha or another similar tool to compute any necessary sums or integrals, and for your matrix calculations. If you have trouble with this, let me know.}\\
%\textbf{If you're using facts about distributions to answer the questions, be very clear about which distribution you're using to model that problem and why that distribution is appropriate.}
\underline{\textbf{Every step of your answers must be fully justified to receive credit.}}
\begin{enumerate}
\item Prove by induction that $\displaystyle\sum_{k=0}^n (k \cdot k!) = (n+1)!-1$ for all $n \geq 1$.
\item Prove the Principle of Inclusion-Exclusion by induction: For any $n \geq 1$ if $A_1, \ldots, A_n$ are finite subsets of a sample space $\Omega$, then
\[
\P\left(\bigcup_{i=1}^{n} A_i\right) = \ds\sum_{\substack{S \subseteq [n]\\S \neq \emptyset}} \left[(-1)^{|S|-1}\P\left(\bigcap_{j\in S} A_j\right)\right].
\]
Here are some facts (hints, really) that you may find useful. If you use them in your proof, you must justify why they are true.
\begin{itemize}[label={$\diamond$}]
\item $\displaystyle\bigcup_{i=1}^{n+1} A_i = \left(\displaystyle\bigcup_{i=1}^n A_i\right) \cup A_{n+1}$
\item $\left(\displaystyle \bigcup_{i=1}^n A_i\right) \cap A_{n+1} = \displaystyle\bigcup_{i=1}^n (A_i \cap A_{n+1})$
\item $\{S : S\subseteq[n]\text{ and }S \neq \emptyset\} \cup \{S\cup\{n+1\} : S \subseteq [n]\text{ and }S \neq \emptyset\} \cup \{\{n+1\} \} = \{S : S \subseteq [n+1]\text{ and }S \neq \emptyset\}$
\end{itemize}
\item After class, $n$ students go straight to a party. They all drop their backpacks in a big pile at the front door. After a long and rambunctious party the students are too distracted to pay attention to which backpack they pick up as the leave. As a result, each student randomly picks a backpack from the pile on their way out -- they pick any remaining backpack with equal probability. What is the probability that no student ends up with their own backpack?\\[10pt]
\emph{Hints:} Let $S_i$ be the event that student $i$ does get their own backpack. What is $\P(S_i)$? If $i \neq j$, what is $\P(S_i \cap S_j)$? If $M \subseteq [n]$, what is $\P\left(\bigcap_{k \in M} S_k\right)$? The final answer we're looking for is $\P\left(\overline{\bigcup_{i=1}^n S_i}\right)$. Use the Principle of Inclusion-Exclusion to calculate this.
\item You have two identical opaque bags. One contains a red ball and a yellow ball, while the other contains two red balls. First you pick one of the bags at random. Then you sample a ball from that bag with replacement $n$ times. If you draw a red ball all $n$ times, what is the probability that the bag you're using is the one with two red balls?
\item Give an example of a sample space and three events $A$, $B$, and $C$ such that each pair $(A,B)$, $(A,C)$, $(B,C)$ is pairwise independent, but the triple $(A,B,C)$ is not mutually independent.
\item Prove that if $S$ and $T$ are independent events, then $\overline{S}$ and $\overline{T}$ are independent events.
\item Two friends, Joel and Sheila, are shooting basketballs on a court at the same hoop. Joel sinks 25\% of his shots while Sheila hits 75\% of her shots. Suppose they both take a shot at the same time and exactly one basketball goes through the hoop. Assuming the success of the shots is independent, what is the probability that the one that went in was shot by Sheila?
\end{enumerate}
\end{document}