A calculus of the absurd

4.12.5 The Cauchy-Schwarz inequality

This is a really significant inequality which is useful for proving lots of things. The Cauchy-Schwarz inequality states that for any sequence of real numbers \(a_1, a_2, ..., a_n\) and \(b_1, b_2, ..., b_n\), the pairwise products are less than products of the square roots of the sum of the squares, that is, that

\begin{equation} a_1 b_1 + a_2 b_2 + ... + a_n b_n \leqq \sqrt {(a_1)^2 + (a_2)^2 + ... +(a_n)^2} \sqrt {(b_1)^2 + (b_2)^2 + ... + (b_n)^2} \end{equation}

This theorem says a lot, so it helps to consider what it says in some specific cases, for example if we have the sequences \(1, -1, 5, 12, -64\) and \(-12, 7, 3, 90, 4\) then the Cauchy-Schwarz inequality tells us that

\begin{align} & (1)(-12) + (-1)(7) + (5)(3) + (12)(90) + (-64)(4) \\ &\quad \leqq \sqrt {(1)^2 + (-1)^2 + (5)^2 + (12)^2 + (-64)^2} \\ &\quad \quad \sqrt {(-12)^2 + (7)^2 + (3)^2 + (90)^2 + (4)^2} \end{align}

This is true as (at least when I plugged the numbers into my calculator) the left-hand side is equal to \(820\) (what a nice, whole number) whereas the right-hand side is approximately equivalent to \(5957.59229891\) (which is not a nice, whole number).

Of course, this isn’t a proof - it’s just an example! To prove this in the general case (i.e. for every \(n \in \mathbb {N}\)) there’s a non-zero chance that we should use induction4141 As introduced in Section 6.3 (because whenever we want to prove that some property holds for all natural numbers, it’s likely that induction will help).

How do we prove this in the general case? Well, let’s apply the principle of mathematical induction.

  • • If \(n=0\) the statement is trivially true (as \(0 \leqq 0\) - note: let’s agree that the sum over \(0\) terms is \(0\)). In case you’re unconvinced that either \(0\) is a natural number (don’t worry, there’s no shame in being wrong) or that the inequality is really defined for \(n=0\), we can also show that it’s true for \(n=1\). As a value is less than or equal to its modulus (as proven in Section 4.9.5)

    \begin{align} a_1 b_1 &\leqq |a_1 b_1| \label {modulus less than} \\ &= \sqrt {(a_1 b_1)^2} & \text {def. modulus function (see Section \ref {modulus as sqrt squared})} \\ &= \sqrt {(a_1)^2} \sqrt {(b_1)^2} \end{align}

  • • Now onto the inductive step. We assume the statement for \(k\) is true (see Equation 4.195) and then our goal (which it is important not to lose sight of, in life as well as mathematics problems) is to show that the statement is also true for \(n=k+1\) (this is an example of going from \(k\) to \(k+1\), rather than trying to spot the case of \(k\) lurking inside the case of \(k+1\) - see Section 6.3.2)

    \begin{equation} a_1 b_1 + a_2 b_2 + ... + a_k b_k \leqq \sqrt {(a_1)^2 + (a_2)^2 + ... +(a_k)^2} \sqrt {(b_1)^2 + (b_2)^2 + ... + (b_k)^2} \label {Cauchy-Schwarz for n=k} \end{equation}

    We would like to make this inequality true for the case of \(k+1\), so we should do something to manipulate its structure which gives us this case. There are two options, trying to add an \((a_{k+1})^2\) (and also the same for \(b\)) inside the square roots, or perhaps we can try adding \(a_{k+1}b_{k+1}\) to both sides. I know which one I prefer (the latter).

    \begin{align} a_1 b_1 + ... + a_k b_k + a_{k+1} b_{k+1} &\leqq \sqrt {(a_1)^2 + ... +(a_k)^2} \sqrt {(b_1)^2 + ... + (b_k)^2} + a_{k+1} b_{k+1} \end{align}

    Now we need to try to combine \(a_{k+1} b_{k+1}\) by using operations which either leave the value of the right-hand side the same, or make it bigger. In the end, we would like a square root, and we do know one way to make a bigger expression out of the numbers \(\sqrt {(a_1)^2 + ... +(a_k)^2} \sqrt {(b_1)^2 + ... + (b_k)^2}\) and \(a_{k+1} b_{k+1}\); the inequality we are trying to prove, but for the case \(n=2\) (which is fantastic because proving the statement for \(n=2\) is a great deal easier than proving it for all \(n\)). Therefore, applying the Cauchy-Schwarz inequality in the case where \(n=2\), accepting that we have sacrificed some generality (which we will need to regain by proving that the statement is true for \(n-2\)) this is less than or equal to

    \begin{align} a_1 b_1 + ... + a_k b_k + a_{k+1} b_{k+1} &\leqq \sqrt {\sqrt {(a_1)^2 + ... + (a_k)^2}^2 + (a_{k+1})^2}\sqrt { \sqrt {(b_1)^2 + ... +(b_k)^2} + (b_{k+1})^2 } \\ &= \sqrt {(a_1)^2 + ... + (a_k)^2 + (a_{k+1})^2}\sqrt { (b_1)^2 + ... +(b_k)^2 + (b_{k+1})^2 } \end{align} TODO: proof for case \(n=2\)