\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}Solution:\quad 
\color{red} #1
\end{quote}
}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}(#1)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\begin{document}
\title{Math 301: Homework 1}
\author{Mary Radcliffe}
\date{due 8 Sept 2017}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Suppose you have a set of voters, and they will each vote Yes or No on a certain proposition. If we order the voters, with all the Yes votes going first, then the voter whose Yes vote clinches the proposition is said to be pivotal. For example, if there are 5 voters, and 3 yesses are required to pass the proposition, then whoever is third is the pivotal voter.

The Shapley Power index of a voter is defined to be the proportion of orderings for which that voter is pivotal. In the case of our 5 voter example, a voter is pivotal every time they appear in the third position. Hence their power index would be 
\[ \frac{\hbox{\# of times appears third}}{5!}=\frac{4!}{5!}.\]

The United States Federal system has 100 senators and 435 representatives. A bill passes both chambers if it receives at least 51 votes from the Senate and at least 216 votes from the House. We shall ignore filibusters and presidential votes.

Determine the Shapley Power indices of a US senator and a US representative.

\item Let $k$ and $n$ be integers such that $0\leq k\leq n-1$. Provide a combinatorial proof of the identity
\[\sum_{j=0}^k{n\choose j}= \sum_{j=0}^k{n-1-j\choose k-j}2^j.\]
(Note: by a ``combinatorial proof," we mean a proof that is based on counting, rather than an algebraic proof.)


\item For $a, b\in \Z$, let $L(a, b)$ denote the set of lattice paths from $(0,0)$ to $(a, b)$.

Fix $n\in \Z$, and let $1\leq k\leq n-1$. Construct an injective function  \[F:L(k-1, n-k+1)\times L(k+1, n-k-1)\to L(k, n-k)\times L(k, n-k).\] Use this to prove that for all $k\leq n-1$, \[{n\choose k-1}{n\choose k+1}\leq {n\choose k}^2.\] (This property is called {\it log-concavity}. That is, a sequence $a_0, a_1, \dots, a_n$ is called log-concave if for all $1\leq k\leq n-1$, we have $a_{k-1}a_{k+1}\leq a_ka_k$. Hence, here we are proving that the sequence ${n\choose 0}, {n\choose 1}, \dots, {n\choose n}$ is log-concave.)

\item Define that the M\"{o}bius function $\mu(n)$ to be 0 if n contains a square factor and $(-1)^r$ if $n$ is the product of $r$ distinct primes. For any $n \geq 2$, use the principle of Inclusion/Exclusion to prove that $\sum_{d | n} \mu(d)=0$.


\end{enumerate}

\end{document}