Tricki
a repository of mathematical know-how

Prove a consequence first

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.

Prerequisites

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

Comments

Independent

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.

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications