\problemdata
{induction}
{S00 ps2}
{solutions of equation}

\begin{problem}
% ordinary induction
% source: fall98

Prove by induction on $n$ that for all $n \geq 0$, the inequality $|x|
+ |y| \leq n$ has exactly $2 n^2 + 2n + 1$ solutions where $x$ and $y$
are integers.

\solution{
  Let $P(n)$ be the proposition that there are $2 n^2 + 2n + 1$
  solutions to the inequality $|x| + |y| \leq n$, where $x$ and $y$
  are integers.  We prove that $P(n)$ holds for all $n \geq 0$ by
  induction on~$n$.

  In the base case, $P(0)$ is true because $2 (0)^2 + 2 (0) + 1 = 1$
  and there is one solution to the equation $|x| + |y| \leq 0$, namely
  $x = y = 0$.  This is easily argued by contradiction.  Without loss
  of generality, suppose that $x$ is not zero.  Then, since $|z| \geq
  0$, for all $z$, and $|z| > 0$, for all $z \not = 0$, it follows
  that $|x| + |y| > 0$; a contradiction.  Thus, $x$ must be zero.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.  That is, we
  want to prove that there are $2 (n+1)^2 + 2 (n + 1) + 1 = 2n^2 + 6n
  + 5$ solutions to the inequality $|x| + |y| \leq n + 1$.  Every
  solution to this inequality is also either a solution to the tighter
  inequality $|x| + |y| \leq n$ or else to the equation $|x| + |y| = n
  + 1$.  Thus, the number of solutions is equal to the number of
  solutions to the tighter inequality plus the number of solutions to
  the equation.

  By the inductive hypothesis, there are $2 n^2 + 2n + 1$ solutions to
  the tighter inequality.  All that remains is to count solutions to
  the equation.  The value of $x$ must be in the range $-(n+1),
  \ldots, n+1$.  If $x$ takes on either of the two values $-(n+1)$ or
  $n+1$, then there is a single solution, with $y = 0$.  If $x$ takes
  on one of the $2n+1$ values in the range $-n, \ldots, n$, then there
  are two solutions, one with $y = n + 1 - |x|$ and one with $y = -(n
  + 1 - |x|)$.  Thus, there are $2 + 2 \cdot (2n + 1) = 4n + 4$
  solutions to the equation and $2 n^2 + 2n + 1$ solutions to the
  tighter inequality, giving $2 n^2 + 6n + 5$ solutions in all, as
  desired.  Therefore, $P(n)$ implies $P(n+1)$, which concludes the
  inductive step.
}
\end{problem}
