# How does one begin to even write a proof?

I'm in my first proof based class and I'm just having a lot of trouble writing proofs. I mean I know it's not going to come natural and it will take time, but seroiusly, how does someone begin to write a proof and formulate a game plan? For example, I'm trying to write up a solution for this problem but I can't seem to figure out where to start.

Given $y \in \mathbb R, n\in\mathbb N$, and $\epsilon \gt 0$, show that for some $\delta \gt 0$, if $u\in \mathbb R$, and $|u-y|\lt \delta$, then $|u^n-y^n|\lt \epsilon$.

Any suggestions on how to start or even what some first things I should think about are when faced with a "Show that..." problem? I'm really looking for a combination of where to start for this and some proof writing in general.

-
You begin to write a proof by reading lots of proofs and seeing how they go and then going the same way. – Gerry Myerson Jan 30 '13 at 6:32
@GerryMyerson Thank you... That actually makes complete sense.. – TheHopefulActuary Jan 30 '13 at 6:37
There are a lot of variables here. My advice would be that whatever variables you are given (in this case, $y$, $n$, and $\epsilon$), you should consider as fixed for the remainder of the problem. Fixing some variables in your mind might let you focus on the other "more variable" ones. – Jesse Madnick Jan 30 '13 at 22:58
Attitude to the problem is important. If you want to solve it at all costs, you'll end up depressed, psychologically unbalanced with the rest of our life suffering. On the other hand, if you see the proof as secondary and the knowledge and experience gained from working on it primary, you have far more chance of proving it in the long run. – user10389 Jan 31 '13 at 17:30

Here are a some steps that I find useful when writing proofs, not necessarily in order.

1. If the statement of the problem uses terms you aren't entirely comfortable with, translate it into simpler language, or even paraphrase the problem in regular English. For example, a statement about the linearity of the derivative might be shortened to "the sum of the derivatives is the derivative of the sum".

2. Determine the hypotheses you have to work with. One of the worst things you can try and do is to attack the problem from first principles alone. If you are giving specific hypotheses, start with them! It's quite possible that your conclusion is false without those hypotheses.

3. Figure out what, exactly, you are being asked to show. You might find yourself running in circles if you don't have a clear direction in mind.

4. Look at the relevant chapter(s) of your textbook, and see what theorems relate to the hypotheses you are given. I cannot stress this enough. If your hypothesis is that "$f$ is continuous on a compact set", look at every lemma and theorem in the chapter that begins: "Let $f$ be continuous on a compact set...", even if further assumptions are necessary.

5. Often, if you are given many hypotheses, try and figure out how they work together. A continuous function on a compact set is better than a continuous function and a compact set (as seperate objects).

6. Ask yourself: "Is there any statement or result that would help me get to my conclusion? Is there anything that would help if it were true?" This is how you make your own lemmas and propositions.

7. Most Importantly: After you've translated the problem into a context you understand, ask yourself "why should this be true?" It might help to draw a picture, or consider some explicit examples. In my experience, when it comes to writing proofs, especially in analysis, if you don't know why something should be true, you'll have a hell of a time trying to prove it. When you can convince yourself why something should be true, all that's left is to translate that intuition into rigorous mathematics. While that requires some technical skill, that is something you will pick up over time -- in the long run, the intuitive answer is often the most important part.

-
Excellent overview of the general strategy. My only suggestion is to show how some of this can be applied to the given statement--I think the most important points might be obscured because the OP has not seen many proofs in action. – peoplepower Jan 30 '13 at 7:01
This is a very good answer. Points 2, 3, 4 are exactly what I would've said. – Jesse Madnick Jan 30 '13 at 22:54
You must go on some very interesting dates. – Gerry Myerson Jan 31 '13 at 5:42
A couple, actually. – Isaac Solomon Jan 31 '13 at 5:44
When you want to show that two things are equal, but some things are defined in terms of limits, the way you show they are equal is by showing you can make them within $\epsilon$ by going far out enough in the limit. That is a very general sort of situation in which $\forall \epsilon > 0 ...$ is appropriate. – Isaac Solomon Feb 1 '13 at 2:48

Isaac’s sixth point is especially applicable when you’ve reason to expect that the proof will be relatively straightforward $-$ not necessarily easy, but not requiring enormous insight or cleverness $-$ as is the case here. Note that that would help me get to my conclusion can (and often should) be interpreted pretty broadly: I might say simply that provides some clear connection between what I’m given and what I want to get from it.

In this case you’re trying to impose a condition on $|u-y|$ that affects $|u^n-y^n|$; what relationship(s) do you know connecting $u-y$ and $u^n-y^n$? There’s only one that springs to my mind: the factorization

$$u^n-y^n=(u-y)\left(u^{n-1}+u^{n-2}y+\ldots+u^{n-1-k}y^k+\ldots+uy^{n-2}+y^{n-1}\right)$$

or, more compactly, $$u^n-y^n=(u-y)\sum_{k=0}^{n-1}u^{n-1-k}y^k\;.\tag{1}$$

You want to know how small you have to make $|u-y|$ in order to get $|u^n-y^n|$ less than some positive $\epsilon$. If $(1)$ had the form $u^n-y^n=(u-y)M$ for some constant $M$, that would be an easy task, but the summation in $(1)$ obviously isn’t a constant. What if it were bounded? What if you could find an $M$ such that

$$\left|\sum_{k=0}^{n-1}u^{n-1-k}y^k\right|\le M\;,$$

at least for all values of $y$ ‘close enough’ to $u$?

First spoiler:

Then you could use $(1)$ to say that $|u^n-y^n|\le M|u-y|$, at least for all $y$ sufficiently close to $u$, and taking $\delta=\dfrac{\epsilon}M$ would do the trick. And now you’ve reduced your problem to figuring out how to bound $\left|\sum_{k=0}^{n-1}u^{n-1-k}y^k\right|$. You can’t do this in general, but maybe you can do it if you don’t let $u$ get too far away from $y$.

Second spoiler:

What if you decide that no matter what else you require of $\delta$, you’ll make sure that $\delta\le 1$, so that $|u|\le|y|+1$? Can you now find an upper bound for $\left|\sum_{k=0}^{n-1}u^{n-1-k}y^k\right|$ in terms of $|y|+1$, say? That would do, because you’re looking at a fixed $y$.

-
Minor correction to this excellent advice: in the question, it's $y$ that is fixed rather than $u$. – Erick Wong Jan 31 '13 at 5:55
@Erick: Thanks: fixed. (Done in by my own notational tendencies!) – Brian M. Scott Jan 31 '13 at 17:05

To add to Gerry's suggestion, I remember hearing a comment of the composer Ravel: he said "Copy. If you have some originality, then this may come out as you copy. If not, then never mind." I would add that the originality may come out only after you copied several, or many times. I have also heard it said that Newton was an inveterate copier.

So rather than just read proofs, I would suggest you copy proofs by hand, and this may get you gradually into the rhythm of them. Also, you can ask: "What is the key idea?"

In constructing proofs, you also have to learn to work from both ends, forward from the assumptions, and backwards from the conclusion, and hope they meet! Proofs are rarely constructed linearly, you need to know where you are going.

In teaching analysis, I also used the "fill-in" kind of exercise. Take a complicated proof, such as the product of limits is the limit of the product, write it out, then blank out bits, and ask the students to fill in the blanks, giving lots of clues from the parts that are still there. Thus the whole structure of the proof is there, but the students have to use the clues from what is there to complete the details. An advantage is that solutions are easy to mark!

The teaching method behind this is known as "reverse chaining" or "backward chaining", see wikipedia, for example. In other words, the first task you give is to complete something easy. Then you gradually make it more difficult, or start at an earlier stage. The method is a standard training technique, for say animal training, or teaching a child to put on its clothes. The child learns from success, so you arrange for it to be successful! Learning mathematics at any level has some of the same character. It is also how you learn to do many puzzles such as Sudoku, or crosswords, start with the easy ones.

-

Read Pólya's excellent "How to prove it", it is full of advise on how to tackle proving stuff. Hammack's "The Book of Proof" is a detailed discussion of different ways of proving things.

In your case (as in many others, very commonly each time you engage in the $\epsilon$ -- $\delta$ dance) it helps starting at the end and looking how to get to the beginning from there. Once you have that, retracing steps is usually easy.

-
Pólya's book is gold, haven't read Hammack's. I would also recommend "Solving Mathematical Problems - A Personal Perspective" by Terence Tao. – MGA Aug 16 '14 at 13:06

Start to write a chain of consecutive estimates on $|u^n - y^n|<\dots$ (using $|u-y|<\delta$ somewhere) and find condition on $\delta$ so that at the end you arrive up to $\ldots<\epsilon$.

-
In the case of this question, one could argue: the statement required to prove is that the real function $x^n$ is continuous. It is easy to prove that the identity function $x$ is continuous, and we might as well assume, or prove separately, that the product of continuous functions is continuous. Since $x^n=x^{n-1}.x$, the result follows by induction. – Ronnie Brown Jan 31 '13 at 18:04

I found these series of video lectures informative about how to write proofs.

Specifically its good for beginners on how to start writing a proof.

Topology Without Tears - Writing Proofs in Mathematics

Even if it comes with a book about topology its about writing proofs in general.

-