Section 2.1 Mathematical Induction and the Cauchy-Schwarz Inequality
January 8th, 2022
The Cauchy-Schwarz Inequality is a semi-obscure mathematical theorem, and one which I would wager most first-year undergraduate students haven't heard of before. Essentially, it has to do with squares of sums of real-valued sequences.
In this section, I'd like to take a crack at proving the Cauchy-Schwarz Inequality using my personal favourite proof technique: mathematical induction. This proof is one which I formulated independently — I was inspired to do so after seeing a related problem posted on a Discord server I visit.
Mathematical induction is a great tool to have your inventory, but is sort of a hassle to explain, so I won't do that here. Use the power of the internet! Some sources which I think do a good job covering the topic are here and here.
Subsection 2.1.1 Laying the Proverbial Groundwork
The version of the Cauchy-Schwarz Inequality which follows this paragraph — and which we're going to prove — is a bit abridged, for the sake of simplicity. Don't worry, it's still perfectly valid. It's just missing an extra condition for equality.
As previously mentioned, the proof which I give in this section is how I originally proved this theorem myself. It isn't very elegant, but I believe it follows straightforward lines of reasoning, which makes it relatively accessible. It also mainly relies on high-school level algebra.
Theorem 2.1.1. Cauchy-Schwarz Inequality (Truncated).
For all sequences of real numbers \(a_{i}\) and \(b_{i}\text{,}\) the following inequality holds:
\begin{equation*}
\left( \sum_{i = 1}^{n} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{n} a_{i}^2 \right) \left( \sum_{i = 1}^{n} b_{i}^2 \right)\text{.}
\end{equation*}
From the statement of the theorem, it should become apparent why one might be motivated to use mathematical induction as the proof technique. In this context, \(n\) can only assume values in \(\mathbb{Z}^+\text{,}\) so it makes for a good opportunity to utilize induction.
So then, let's get started on that proof! First, we'll consider the base case of \(n = 1\text{,}\) which is quite trivial. We see that
\begin{equation*}
(a_{1} b_{1})^2 \leq a_{1}^2 b_{1}^2\text{,}
\end{equation*}
which is obviously true. The crux of the proof lies in showing that
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) \implies \left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right)
\end{equation*}
holds for all \(k \in \mathbb{Z}^+\text{.}\)
Subsection 2.1.2 It's Always the Algebra...
We want to make use of our inductive step, which is our assumption that
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right)\text{.}
\end{equation*}
This should motivate us to express \(\left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2\) in terms of \(\left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2\text{.}\) Let's write the left hand side out:
\begin{equation*}
\left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 = (a_1 b_1 + a_2 b_2 + ... + a_{k} b_{k} + a_{k+1} b_{k+1})(a_1 b_1 + a_2 b_2 + ... + a_{k} b_{k} + a_{k+1} b_{k+1})\text{.}
\end{equation*}
How does this quantity differ from the other one? Well, note that in addition to the multiplication of
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 = (a_1 b_1 + a_2 b_2 + ... + a_{k} b_{k})(a_1 b_1 + a_2 b_2 + ... + a_{k} b_{k})\text{,}
\end{equation*}
we also require the last term, \(a_{k+1} b_{k+1}\text{,}\) in the left factor to be distributed to all the terms in the right factor, and vice versa. Since the two factors are the same, that'll result in an additional quantity of
\begin{equation*}
2 \cdot (a_1 b_1 a_{k+1} b_{k+1} + a_2 b_2 a_{k+1} b_{k+1} + ... + a_{k} b_{k} a_{k+1} b_{k+1} + a_{k+1} b_{k+1} a_{k+1} b_{k+1})\text{.}
\end{equation*}
Therefore,
\begin{equation*}
\left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 = \left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right)\text{.}
\end{equation*}
Feel free to expand these summations to double-check. Now, the appearance of the middle term marks a good time to invoke the inductive step:
\begin{align*}
\left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 \amp = \left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right)\\
\amp \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right).
\end{align*}
This is a good time to compare the quantity
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right)
\end{equation*}
with that of
\begin{equation*}
\left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right)\text{.}
\end{equation*}
Namely, if we can show that the top quantity is less or equal than the bottom quantity, then the proof is complete. Let's expand this latter quantity out:
\begin{equation*}
\left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right) = (a_1^2 + a_2^2 + ... + a_{k}^2 + a_{k+1}^2)(b_1^2 + b_2^2 + ... + b_{k}^2 + b_{k+1}^2)\text{.}
\end{equation*}
In a manner similar to what occurred previously, we observe that 1
\begin{align*}
(a_1^2 + a_2^2 + ... + a_{k}^2 + a_{k+1}^2)(b_1^2 + b_2^2 + ... + b_{k}^2 + b_{k+1}^2) = \text{ } \amp (a_1^2 + a_2^2 + ... + a_{k}^2)(b_1^2 + b_2^2 + ... + b_{k}^2) \text{ } +\\
\amp (a_1^2 b_{k+1}^2 + a_2^2 b_{k+1}^2 + ... + a_{k}^2 b_{k+1}^2 + a_{k+1}^2 b_{k+1}^2) \text{ } +\\
\amp (a_{k+1}^2 b_1^2 + a_{k+1}^2 b_2^2 + ... + a_{k+1}^2 b_{k}^2 + a_{k+1}^2 b_{k+1}^2).
\end{align*}
It's not real math unless it runs off the page!
In summation notation, we obtain
\begin{equation*}
\left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right) = \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + \left( \sum_{i = 1}^{k+1} a_{i}^2 b_{k+1}^2 + a_{k+1}^2 b_{i}^2 \right)\text{.}
\end{equation*}
Subsection 2.1.3 Approaching an Apex; Alternatively, an Apotheosis
At this point, we should begin to envision what the final result will look like. If we could show the following, then we would have a complete proof:
\begin{align*}
\left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 \amp = \left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right)\\
\amp \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right)\\
\amp \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + \left( \sum_{i = 1}^{k+1} a_{i}^2 b_{k+1}^2 + a_{k+1}^2 b_{i}^2 \right)\\
\amp = \left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right).
\end{align*}
So far, we have shown the first, second, and fourth (in)equalities to be true. The last obstacle to overcome in order to finish this induction proof is to show that
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + 2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right) \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) + \left( \sum_{i = 1}^{k+1} a_{i}^2 b_{k+1}^2 + a_{k+1}^2 b_{i}^2 \right)\text{.}
\end{equation*}
This is, of course, equivalent to showing that
\begin{equation*}
2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right) \leq \left( \sum_{i = 1}^{k+1} a_{i}^2 b_{k+1}^2 + a_{k+1}^2 b_{i}^2 \right)\text{.}
\end{equation*}
Let's see what these would look like written out 2 :
\begin{equation*}
2(a_1 a_{k+1} b_1 b_{k+1} + a_2 a_{k+1} b_2 b_{k+1} + ... + a_{k} a_{k+1} b_{k} b_{k+1} + a_{k+1} a_{k+1} b_{k+1} b_{k+1}) \leq (a_1^2 b_{k+1}^2 + a_{k+1}^2 b_1^2) + (a_2^2 b_{k+1}^2 + a_{k+1}^2 b_2^2) + ... + (a_{k}^2 b_{k+1}^2 + a_{k+1}^2 b_{k}^2) + (a_{k+1}^2 b_{k+1}^2 + a_{k+1}^2 b_{k+1}^2)\text{.}
\end{equation*}
Writing the sums out isn't necessary, but I think it helps one get a sense of the algebra. Also, sorry about this line being ridiculously long.
At this point, my line of reasoning resembled something like this: "The left and right-hand sides are both sums of k+1 terms. If I could show that each term on the left is less than or equal to its respective term on the right, then I'd be done".
That is, by the way, exactly what we're going to show. Do the quantities \(a_1^2 b_{k+1}^2 + a_{k+1}^2 b_1^2\) and \(2(a_1 a_{k+1} b_1 b_{k+1})\) remind you of anything?
What if they were re-written as \((a_1 b_{k+1})^2 + (a_{k+1} b_1)^2\) and \(2(a_1 b_{k+1} \cdot a_{k+1} b_1)\text{?}\) I won't keep you in suspense anymore — we're going to make use of the fact that \(p^2 + q^2 \geq 2pq\) for all \(p, q \in \mathbb{R}\) 3 .
\begin{align*}
(p - q)^2 \amp \geq 0\\
\implies p^2 + q^2 - 2pq \amp \geq 0\\
\implies p^2 + q^2 \amp \geq 2pq.
\end{align*}
It follows immediately from said fact that
\begin{equation*}
2(a_i a_{k+1} b_i b_{k+1}) \leq (a_i^2 b_{k+1}^2 + a_{k+1}^2 b_i^2)
\end{equation*}
for all \(i \in \{1, 2, 3, ..., k, k + 1\}\text{.}\) Then we have shown on a term-by-term basis that
\begin{equation*}
2\left( \sum_{i = 1}^{k+1} a_{i} a_{k+1} b_{i} b_{k+1} \right) \leq \left( \sum_{i = 1}^{k+1} a_{i}^2 b_{k+1}^2 + a_{k+1}^2 b_{i}^2 \right)\text{.}
\end{equation*}
At last, we have shown that
\begin{equation*}
\left( \sum_{i = 1}^{k} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{k} a_{i}^2 \right) \left( \sum_{i = 1}^{k} b_{i}^2 \right) \implies \left( \sum_{i = 1}^{k+1} a_{i} b_{i} \right)^2 \leq \left( \sum_{i = 1}^{k+1} a_{i}^2 \right) \left( \sum_{i = 1}^{k+1} b_{i}^2 \right)
\end{equation*}
holds for all \(k \in \mathbb{Z}^+\text{,}\) by the Principle of Mathematical Induction. This therefore proves our truncated version of the Cauchy-Schwarz Inequality. \(\blacksquare\)