Tricki
a repository of mathematical know-how

Revision of Proving equalities and identities from Sat, 13/12/2008 - 23:25

Quick description

This page has links to other pages that discuss techniques for discovering and proving equalities and identities.

General discussion

If one is asked to prove that (x+1)(x+3)(x-5)=x^3-x^2-17x-15, then the most obvious approach is to do a routine calculation – one simply expands out the brackets on the left-hand side and checks that the answer is the polynomial given on the right-hand side. However, in general there are many more interesting ways of proving equality of mathematical objects are equal. Indeed, even for this simple problem about polynomials one can use some theory to solve it, so we shall let it serve as our first non-obvious method for proving equality.

Technique 1: proving that two polynomials are the same by looking at the roots of their difference

Brief summary (Two polynomials of degree d are equal if they take the same value in d+1 different places. Proof: in this case their difference has d+1 roots, but a non-zero polynomial of degree d has at most d roots. For the polynomial above, we can check that the right-hand side has zeros at -1, -3 and 5. Together with the observation that both polynomials take the value -15 when x=0 (or alternatively, if one wants to use a tiny bit more theory, that they both have leading term x^3), we find that they are equal. Although this method was not obviously the best one for this problem, sometimes it definitely is. See this article for some examples. )

Technique 2: double counting

One of the best ways of proving a non-obvious identity is to show that the two sides of the identity count or measure the same set in two different ways. For example, one could prove that \binom n0+\binom n1+\dots+\binom nn=2^n by induction, but a much better proof is to observe that both sides are counting the number of subsets of an n-element set.

This article discusses the technique of double counting in some detail.

Technique 3: using the law of trichotomy

To show that two real numbers x and y are equal, it is often best to prove that it is not the case that x<y and it is not the case that y<x.

Proofs of this kind are discussed in this article.

Technique 4: Axiomatics

How does one prove that the product of 0 and x is 0 in any field? The answer is that one uses the field axioms directly. Here is a proof. By the definition of 0 as an additive identity, 0+0=0. Therefore, (0+0).x=0.x. By the distributive law, the left-hand side is equal to 0.x+0.x, so we deduce that 0.x+0.x=0.x. Adding the additive inverse w of 0.x to both sides we obtain w+(0.x+0.x)=0. By the associativity of addition we can replace the left-hand side by (w+0.x)+0.x, which equals 0+0.x. And by the definition of 0, this is 0.x, and the proof is complete.

How does one come up with proofs of this kind? This question is discussed here.

Technique 5: To prove that two objects are equal, show that in enough circumstances they behave in the same way

The polynomials method was an example of this. Another important one is that if two vectors have the same inner product with enough other vectors then they must be equal.

An example will illustrate what this means. Suppose we have an n-dimensional inner product space and an orthonormal basis e_1,\dots,e_n, and would like to prove that v=\sum_i\langle v,e_i\rangle e_i for every v. We can do so by taking the inner product of v with an arbitrary e_j. On the left-hand side we obtain \langle v,e_j\rangle, while on the right-hand side we obtain \sum_i\langle v,e_i\rangle\langle e_i,e_j\rangle. Since the e_i are orthonormal, this also equals \langle v,e_j\rangle.

This technique is discussed further here.

Parent article

What kind of problem am I trying to solve?