a repository of mathematical know-how

Revision of Prove a consequence first from Sun, 21/03/2010 - 05:34

Quick description

If one wants to show "If A, then B", first find an interesting consequence C of B that looks easier to prove than B itself, but not so simple that it can be immediately deduced from A. Then try to prove "If A, then C". Finally, show "If A and C, then B". The point is that this factors the original problem into two simpler ones. If one believes that the original implication is true, then the two sub-implications must be true also, so one is not "losing" anything by trying this method.

A variant approach, once one has successfully obtained "If A, then C", is to deconstruct that proof in order to find out what made it work; this can then give valuable clues as to how to then prove the stronger statement "If A, then B". This tends to work well when C acts as a "simplified toy model" of B.


Example 1

For instance, if trying to prove an identity of the form "f(n) = c", where f(n) is some expression depending on a parameter n, and c is independent of n, one might first try to establish the simpler statement "f(n) is independent of n", and then to establish "f(n_0) = c" for some special value n_0 of n (note that n_0 could be an asymptotic value, such as infinity).

Note that many proofs of identities by induction are basically of this form.

General discussion

This post is based on the buzz



Proving the consequence first is a great way to simplify a problem.
But I don't understand the example. What exactly does "independent" mean. How can f(n) be independent of n?

Sorry if this is a stupid question, but I would really like to understand this.

is independent of if the

f(n) is independent of n if the value of f(n) does not actually depend on n, i.e. it is constant as a function of n. For instance n-n is independent of n, as it is always 0.

Equivalently, f(n) is independent of n if one has f(n)=f(m) for all n,m.

Thank you

That's a great explanation. Thanks.