Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.2More direct proofs

In creating a direct proof we need to look at our hypotheses, consider the desired conclusion, and develop a strategy for transforming A into B. Quite often you'll find it easy to make several deductions from the hypotheses, but none of them seems to be headed in the direction of the desired conclusion. The usual advice at this stage is “Try working backwards from the conclusion.”  1 

There is a lovely result known as the “arithmetic-geometric mean inequality” whose proof epitomizes this approach. Basically this inequality compares two different ways of getting an “average” between two real numbers. The arithmetic mean of two real numbers \(a\) and \(b\) is the one you're probably used to, \((a+b)/2\). Many people just call this the “mean” of \(a\) and \(b\) without using the modifier “arithmetic” but as we'll see, our notion of what intermediate value to use in between two numbers is dependent on context. Consider the following two sequences of numbers (both of which have a missing entry) \begin{equation*} 2 9 16 23 \rule{12pt}{.5pt} 37 44 \end{equation*} and \begin{equation*} 3 6 12 24 \rule{12pt}{.5pt} 96 192. \end{equation*}

How should we fill in the blanks?

The first sequence is an arithmetic sequence. Arithmetic sequences are characterized by the property that the difference between successive terms is a constant. The second sequence is a geometric sequence. Geometric sequences have the property that the ratio of successive terms is a constant. The blank in the first sequence should be filled with the arithmetic mean of the surrounding entries \((23+37)/2 = 30\). The blank in the second sequence should be filled using the geometric mean of its surrounding entries: \(\sqrt{24\cdot 96} = 48\).

Given that we accept the utility of having two inequivalent concepts of mean that can be used in different contexts, it is interesting to see how these two means compare to one another. The arithmetic-geometric mean inequality states that the arithmetic mean is always bigger. \begin{equation*} \forall a,b \in \Reals, a,b \geq 0 \; \implies \; \frac{a+b}{2} \geq \sqrt{ab} \end{equation*}

In proving this statement we have little choice but to work backwards from the conclusion because the only hypothesis we have to work with is that \(a\) and \(b\) are non-negative real numbers — which isn't a particularly potent tool. But what should we do? There isn't a good response to that question, we'll just have to try a bunch of different things and hope that something will work out. When we finally get around to writing up our proof though, we'll have to rearrange the statements in the opposite order from the way they were discovered. This means that we would be ill-advised to make any uni-directional inferences, we should strive to make biconditional connections between our statements (or else try to intentionally make converse errors).

The first thing that appeals to your humble author is to eliminate both the fractions and the radicals… \begin{equation*} \frac{a+b}{2} \geq \sqrt{ab} \end{equation*} \begin{equation*} \iff \; a+b \geq 2\sqrt{ab} \end{equation*} \begin{equation*} \iff \; (a+b)^2 \geq 4ab \end{equation*} \begin{equation*} \iff \; a^2+2ab+b^2 \geq 4ab \end{equation*}

One of the steps above involves squaring both sides of an inequality. We need to ask ourselves if this step is really reversible. In other words, is the following conditional true? \begin{equation*} \forall x,y \in \Rnoneg, \, \; x \geq y \; \implies \sqrt{x} \geq \sqrt{y} \end{equation*}

Exercise3.2.1

Provide a justification for the previous implication.

What should we try next? There's really no good justification for this but experience working with quadratic polynomials either in equalities or inequalities leads most people to try “moving everything to one side,” that is, manipulating things so that one side of the equation or inequality is zero. \begin{equation*} a^2+2ab+b^2 \geq 4ab \end{equation*} \begin{equation*} \iff \; a^2-2ab+b^2 \geq 0 \end{equation*}

Whoa! We're done! Do you see why? If not, I'll give you one hint: the square of any real number is greater than or equal to zero.

Exercise3.2.2

Re-assemble all of the steps taken in the previous few paragraphs into a proof of the arithmetic-geometric mean inequality.

Subsection3.2.1Exercises

  1. Suppose you have a savings account which bears interest compounded monthly. The July statement shows a balance of $ 2104.87 and the September statement shows a balance $ 2125.97. What would be the balance on the (missing) August statement? \hint{A savings account where we are not depositing or withdrawing funds has a balance that is growing geometrically.}

  2. Recall that a quadratic equation \(ax^2+bx+c=0\) has two real solutions if and only if the discriminant \(b^2-4ac\) is positive. Prove that if \(a\) and \(c\) have different signs then the quadratic equation has two real solutions. \hint{You don't need all the hypotheses. If \(a\) and \(c\) have different signs, then \(ac\) is a negative quantity}

  3. Prove that if \(x^3-x^2\) is negative then \(3x+4 \lt 7\). \hint{This follows very easily by the method of working backwards from the conclusion. Remember that when multiplying or dividing both sides of an inequality by some number, the direction of the inequality may reverse (unless we know the number involved is positive). Also, remember that we can't divide by zero, so if we are (just for example, don't know why I'm mentioning it really…) dividing both sides of an inequality by \(x^2\) then we must treat the case where \(x=0\) separately.}

  4. Prove that for all integers \(a,b,\) and \(c\), if \(a|b\) and \(a|(b+c)\), then \(a|c\).

  5. Show that if \(x\) is a positive real number, then \(x+\frac{1}{x} \geq 2\). \hint{If you work backwards from the conclusion on this one, you should eventually come to the inequality \((x-1)^2 \geq 0\). Notice that this inequality is always true — all squares are non-negative. When you go to write-up your proof (writing things in the forward direction), you'll want to acknowledge this truth. Start with something like “Regardless of the value of \(x\), the quantity \((x-1)^2\) is greater than or equal to zero as it is a perfect square.”}

  6. Prove that for all real numbers \(a,b,\) and \(c\), if \(ac\lt 0\), then the quadratic equation \(ax^{2}+bx+c=0\) has two real solutions. Hint: The quadratic equation \(ax^{2}+bx+c=0\) has two real solutions if and only if \(b^{2}-4ac>0\) and \(a\neq0\). \hint{This is very similar to problem b.}

  7. Show that \(\binom{n}{k} \cdot \binom{k}{r} \; = \; \binom{n}{r} \cdot \binom{n-r}{k-r}\) (for all integers \(r\), \(k\) and \(n\) with \(r \leq k \leq n\)). \hint{Use the definition of the binomial coefficients as fractions involving factorials: E.g. \(\displaystyle\binom{n}{k} \; = \; \frac{n!}{k! (n-k)!}\) Write down the definitions, both of the left hand side and the right hand side and consider how you can convert one into the other.}

  8. In proving the product rule in Calculus using the definition of the derivative, we might start our proof with: \begin{equation*} \frac{\mbox{d} }{\mbox{d} x} \left( f(x) \cdot g(x) \right) \end{equation*} \begin{equation*} = \lim_{h \longrightarrow 0} \frac{f(x+h) \cdot g(x+h) - f(x) \cdot g(x)}{h} \end{equation*} The last two lines of our proof should be: \begin{equation*} = \lim_{h \longrightarrow 0} \frac{f(x+h) - f(x)}{h} \cdot g(x) \; + \; f(x) \cdot \lim_{h \longrightarrow 0} \frac{g(x+h) - g(x)}{h} \end{equation*} \begin{equation*} = \frac{\mbox{d} }{\mbox{d} x}\left( f(x) \right) \cdot g(x) \; + \; f(x) \cdot \frac{\mbox{d} }{\mbox{d} x}\left( g(x) \right) \end{equation*} Fill in the rest of the proof. \hint{The critical step is to subtract and add the same thing: \(f(x)g(x+h)\) in the numerator of the fraction in the limit which gives the definition of \(\frac{\mbox{d} }{\mbox{d} x} \left( f(x) \cdot g(x) \right)\). Also, you'll need to recall the laws of limits (like “the limit of a product is the product of the limits — provided both exist”) }