Tricki

## 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 http://www.google.com/buzz/114134834346472219368/iWPJy7vqQ7s/A-basic-problem-solving-technique-in-mathematics

### 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

is independent of if the value of does not actually depend on , i.e. it is constant as a function of . For instance is independent of , as it is always .

Equivalently, is independent of if one has for all .

### Thank you

That's a great explanation. Thanks.