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.


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



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.