How does one begin to even write a proof?

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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.

Answer 4

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$.

Answer 5

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.