\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath}
\begin{document}
\noindent Geoffrey Thomas
\noindent 18.781 pset 2
\noindent Collaborators: Liz Denys

\begin{enumerate}
\item[3] a. Since coefficients of corresponding terms must correspond, we have that for any $z^k$, the left coefficient $\binom{m+n}{k}$ must equal the sum of the coefficients of all $z^k$ terms on the right side. For any index $i$ in the first summand, which provides a $z^i$ factor, we can get a $z^k$ term by using the index $k-i$ in the second summand. The product of the coefficients is then $\binom{m}{i}\binom{n}{k=1}$. So the sum of the coefficients is the sum we want to equate with $\binom{m+n}{k}$.

b. In order to satisfy these constraints, you need to select $i$ elements from $\mathcal{U}$ and the remainder from $\mathcal{V}$. The number of ways to do this is $\binom{m}{i}\binom{n}{k-i}$.

c. In the equality of part a, replace $m$ and $k$ with $n$, and $i$ with $k$, yielding \[\sum_{k=0}^k \binom{n}{k} \binom{n}{n-k} = \binom{2n}{k}\]. Applying formula 1.10 to convert $\binom{n}{n-k}$ to $\binom{n}{k}$ yields the equality we are looking for.

\item[9] We prove this by induction. First, as a base case, \[\Delta^2 f(x) = \Delta f(x+1) - \Delta f(x) = f(x+2) - f(x+1) - f(x+1) + f(x) = \sum_{j=0}^2 (-1)^j \binom{2}{j} f(x + 2 - j)\] Then 
\begin{align*}
\Delta^{k+1} f(x) & = \Delta^k f(x+1) - \Delta^k f(x) \\
& = \sum_{j=0}^k (-1)^j \binom{k}{j}f(x + 1 + k - j) - \sum_{j=0}^k (-1)^j \binom{k}{j}f(x + k - j) \\
& = \sum_{j=0}^k (-1)^j \binom{k}{j}f(x + 1 + k - j) + \sum_{j=0}^k (-1)^{j+1} \binom{k}{j}f(x + k - j) \\
& = \sum_{j=0}^k (-1)^j \binom{k}{j}f(x + 1 + k - j) + \sum_{j=0}^k (-1)^{j+1} \binom{k}{j}f(x + 1 + k - (j+1)) \\
& = \sum_{j=0}^k (-1)^j \binom{k}{j}f(x + 1 + k - j) + \sum_{j=1}^{k+1} (-1)^j \binom{k}{j-1}f(x + 1 + k - j) \\
& = \sum_{j=0}^{k+1} (-1)^j \binom{k}{j}f(x + 1 + k - j) + \sum_{j=0}^{k+1} (-1)^j \binom{k}{j-1}f(x + 1 + k - j)
\end{align*}
where we are temporarily defining $\binom{k}{-1} = 0$ for convenience: this definition satisfies the recursive definition 1.14 of the bionmial coefficients. We can now combine the sums and apply that definition to yield \[sum_{j=0}^{k+1) (-1)^j \binom{k+1}{j}f(x + (k+1) - j)\] which finishes the recursive case.

\item[11] \[\binom{x}{k} = \frac{1}{k!} x (x-1) (x-2) \cdots (x-k+1)\] which is a polynomial of degree $k$ and leading coefficient $1/k!$.

We can express $P(x)$ in the desired form by matching coefficients from the highest-degree term downwards. Since the only expression in the sum that is of degree $n$ is $c_n \binom{x}{n}$, we set $c_n = k!$ times the coefficient of the $x^n$ term in $P(x)$. This uniquely defines $c_n$. Then we can set $c_{n-1}$ to the value to make the $x^{n-1}$ term in our representation have the appropriate coefficient, which is again uniquely determined because only the $c_n \binom{x}{n}$ and $c_{n-1} \binom{x}{n-1}$ expressions have terms of degree $n-1$, and $c_n$ has been previously determined. Then repeat for $n-2$, etc. by strong induction.

\item[12] By 1.14, \[\binom{x+1}{k} - \binom{x}{k} = \binom{x}{k-1} + \binom{x}{k} - \binom{x}{k} = \binom{x}{k-1}\].

Apply the formula for $\Delta$ to each term in turn.

\item[15] The book demonstrates that $\binom{n}{k}$ is always an integer if $n$ and $k$ are integers. We can determine the $c_k$ by working forwards from $P(0)$ up: since $\binom{0}{k}$ is 1 for $k=0$ and 0 otherwise, $c_0$ must equal $P(0)$, an integer. Then consider $P(1)$. We have an integer value for the $c_0 \binom{1}{0}$ term, and $\binom{1}{k}$ is 1 for $k=1$ and $0$ for all higher $k$, so $c_1$ is determined as $P(1)$, an integer, minus some integer result we already have. In the same fashion proceed by strong induction to set all the $c_i$s to integers. Then, since $\binom{x}{k}$ is integer-valued for $k$ an integer, our representation is also integer-valued.

\item[12] In order for 19 to be a divisor of $4n^2+4$, we would need
\begin{align*}
4n^2+4 & \equiv 0 \mod 19 \\
4n^2   & \equiv -4 \mod 19 \\
 n^2   & \equiv -1 \mod 19
\end{align*}

But 19 is congruent to 3 mod 4, so by theorem 2.12 this equation has no solutions.

\item[17] By Wilson's theorem, $70! \equiv -1 \pmod{71}$. So to demonstrate that $61! \equiv 63! \equiv 70! \pmod{71}$, we just need to show that the factors between them, i.e., $62 \cdot 63$ and $64 \cdot 65 \cdots 71$, are congruent to 1 modulo 71. But we can replace these with equivalent residues: the first is $-9 \cdot -8 \equiv 72 \equiv 1 \pmod{71}$, and the second is $-7 \cdot -6 \cdots -1 = -72 \cdot 70 = 1 - 71^2 \equiv 1 \pmod{71}$.

\item[30] By Euler's theorem $3^{\phi(100)} \equiv 1 \pmod{100}$. $\phi{100} = 40$ (of the 50 odd integers, 10 share 5 as a common factor), so $3^400 \equiv {3^40}^10 \equiv 1 \pmod{100}$. So the last two digits are 01.

\item[38]p