Problem 3

Proceed as follows:

• Randomly ${2}$-color the integers. Let ${A}$ be a ${k}$-AP. Calculate the probability that ${A}$ is monochromatic.
• In HW 7, \#3 you computed the number of ${k}$-APs in ${[1,n]}$. Use this to show that the probability that a monochromatic ${k}$-AP exists in ${[1,n]}$ is

$\displaystyle \frac{n^2}{(k-1)2^k} (1+ o(1)).$

• Argue that for large enough ${k}$, ${n = 2^{k/2}}$ will make this less than ${1}$.

Problem 4

Here is a `template’: We show that ${+}$ is primitive recursive.

Then we argue as follows:

• We put ${f(0,y) = g(y)}$ with ${g = p_1}$, the identity. ${g}$ is primitive recursive since ${p_1}$ (projection of a unary function in the first coordinate) is.
• We put ${f(x+1,y) = h(x,y,f(x,y))}$, where ${h = S \circ p_3}$. ${h}$ is primitive recursive since successor ${S}$ and projection ${p_3}$ are, and the primitive recursive functions are closed under substitution (4).
• By closure under primitive recursion (5), ${f}$ is primitive recursive, and ${f}$ defines ${+}$.