A calculus of the absurd

4.12.3 Adding or removing terms

It seems “obvious”⁴⁰⁴⁰ But be careful; so does the pigeonhole principle (Section 6.5) and applying that is far from obvious to say that if \(a \leqq b\) then the validity of the inequality is unchanged by any operation which either makes \(a\) smaller or \(b\) bigger, for example, if we have \(a \leqq b\), then both of these inequalities must also be true

\begin{align} & a \leqq b + 1 \\ & a - 1 \leqq b \end{align}

Or, more generally, for any \(x > 0\), \(a \leqq b\) implies that both

\begin{align} & a \leqq b + x \\ & a - x \leqq b \end{align}

This is a fundamental (read: very useful) principle for manipulating inequalities.

Example 4.12.1 Show that \(n! \geqq \left (\frac {n}{2}\right )^{\frac {n}{2}}\)

As when proving identities (see Section 6.2), we can prove this by starting with one side of the inequality and showing that this is smaller/larger than the other half. Starting with \(n!\) we can apply the definition, which gives the equality that

\begin{align} n! &= n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1 \\ \end{align}

We now want to make the inequality smaller, and not just in any old way; we specifically want to make it smaller and look like \(\left (\frac {n}{2}\right )^{\frac {n}{2}}\). It really helps to consider the structure of \(\left (\frac {n}{2}\right )^{\frac {n}{2}}\) here - i.e. it looks something a bit like \(\frac {n}{2} \times \frac {n}{2} \times ... \times \frac {n}{2}\) (or it would if we could be sure that \(\frac {n}{2}\) was an integer, which we can by rounding \(\frac {n}{2}\) up - it’s fine to show that \(n!\) is bigger than (or equal to) something which is in turn bigger than (or equal to) \(\frac {n}{2}\), as this still proves the fact that we are after - which we can write as \(\left \lceil \frac {n}{2} \right \rceil \)). Let us try to remove some terms to “fit” \(n!\) to \(\left (\frac {n}{2}\right )^{\frac {n}{2}}\)

\begin{align} n! &\geqq n \times (n - 1) \times ... \times \left (\left \lceil \frac {n}{2} \right \rceil \right ) \\ \end{align}

We can then make all the terms smaller, like this

\begin{align} n! &\geqq \left (\left \lceil \frac {n}{2} \right \rceil \right ) \times ... \times \left (\left \lceil \frac {n}{2} \right \rceil \right ) \\ &= \left (\left \lceil \frac {n}{2} \right \rceil \right ) ^{\left \lceil \frac {n}{2} \right \rceil } \\ &\geqq \left (\frac {n}{2}\right )^{\frac {n}{2}}. \end{align}