Feeds:
Posts
Comments

Induction

I’ve had a request to put up a post on induction, since a few people are having trouble with it. Every year people have trouble with induction, perhaps because it’s one of the first methods of formal proof that you see, but hopefully I’ll be able to convince you it really isn’t too bad! The post got pretty long, so I’m going to add the examples as comments at the end, so you can skip down to them if you want.

 

So what is induction? Well let’s say I have to prove a statement about infinitely many things at once, perhaps a statement about each number 1, 2, 3, \ldots. We’ve seen from previous posts that we can’t just check a few examples, we’re interested in a proof that will always hold, so what can we do? The principle of mathematical induction says the following:

Let’s say we know the following two things:

  1. A statement is true for some base number (let’s assume this is 1 for now)
  2. Whenever the statement is true for one number n, it is also true for n+1

then it  follows that the statement is true for all the numbers 1, 2, 3, \ldots.

The principle works like lining up a set of dominoes to knock down. If we know (1) that we can knock over the first domino, and (2) that each domino will hit the next one, then we can infer that all the dominoes will fall down. In the mathematical setting, the first part is called the inductive base, and the second part the inductive step.

If you’re first starting out with induction, you might be a bit dubious here. We want to prove a statement is true, and in step (2), we just assume it’s true, and use that to prove it’s true, there must be something dodgy! Actually, the difference is subtle, but an important part of university mathematics. The difference is in the “for all” vs. “for some” wording which may have come up in other places too. We want to prove a statement for all n, and to do that, in step (2) we assume the statement is true for some n. “For some” just means we assume we can find one place where the statement holds, and induction is a method for starting with one place where something works, and using that to find other places.

Remember: Both ingredients in induction are important. If you only prove the base case, then all you’ve done is proved one special case. If you only prove the step from n to n+1, then for all you know, there might not be a place where that statement is true from which you can construct the other places. It’s like lining up all your dominoes, but not checking you can actually push the first one over.

The examples are now below as comments, but before we go on I’ll just remind you of some notation. We’ll often write “P(n)” for “the statement we’re trying to prove about n”, and it’s important to remember that even though it looks like a mathematical expression, P(n) is a statement. For this reason, P(n) can be true, or false, but it doesn’t really make sense to write things like “P(n)=n^2+1” .

One of the tutors has asked me to put in a quick post about a homework question  you had on rational numbers which many people had trouble with (Sheet 2, Q4). It’s a good question to go through because it’s one of your first tastes of actual analysis, and involves proving something about all rational numbers at once, so it’s good proof practice.

The question was

Prove that for any x, y \in \mathbb{Q}, with x < y, we can find some z \in \mathbb{Q} with x < z < y.

We call this property of the rationals being “dense”, because it means that you can find rational numbers in even the smallest gaps on the number line. The question is asking, if I give you two different rational numbers, can you find another rational number that sits between them.

The first thing to say is that it isn’t enough to check this for some special cases. An answer like the following

Let x=\frac{1}{2} and y=\frac{3}{4}, then

\frac{1}{2} < \frac{5}{8} < \frac{3}{4},

so the result is true.

will score you no marks because it only deals with one case, and since there are infinitely many cases, you really haven’t made much of a dent! That said, checking a few examples is always a good way to get your head round things.

 

So how would you go about proving the statement for all the infinitely many cases? Well the best way is to take two rational numbers called x and y and see if you can find a rational number z which is between them. Once you’ve found this number, you’ll need to prove that

  1. z is a rational number.
  2. z does sit between x and y.

So what number is always between x and y? How about the average of x and y, which is z=\frac{x+y}{2}. Now that we have a candidate, let’s check that it satisfies 1. and 2. above.

  1. Is z rational? To prove it is, we need to write it as \frac{a}{b} for two integers a and b. Well x and y are both rational, so we can write them that way. How about we say x=\frac{x_1}{x_2} and y=\frac{y_1}{y_2}. So
    z \quad= \quad\frac{\frac{x_1}{x_2}+\frac{y_1}{y_2}}{2}\quad=\quad\frac{x_2 y_2}{x_2 y_2}\cdot\frac{\frac{x_1}{x_2}+\frac{y_1}{y_2}}{2}\quad=\quad\frac{x_1 y_2 + y_1 x_2}{2 x_2 y_2}
    But x_1,x_2,y_1,y_2 are all integers, so x_1 y_2 + y_1 x_2 and 2 x_2 y_2 are also integers. So we’ve written z in the form we wanted. The only other thing we need to check that the bottom of the fraction isn’t zero, as that would mess us up, but this is fine, because both x_2 and y_2 come from the bottom of other rational numbers, so neither of them could be zero.
  2. Is z between x and y? Well x<y, so \frac{x}{2}<\frac{y}{2}. So we have
    z \quad = \quad \frac{x+y}{2} \quad = \quad \frac{x}{2} + \frac{y}{2} \quad < \quad \frac{y}{2} + \frac{y}{2} \quad = \quad y.
    For the very same reason, we get
    z \quad = \quad \frac{x+y}{2} \quad = \quad \frac{x}{2} +  \frac{y}{2} \quad > \quad \frac{x}{2} + \frac{x}{2} \quad = \quad x.
    So indeed x<z<y.

So there you go, a proof for infinitely many things at once, which touches on some the things you’ll be doing when you move onto analysis proper, later in the course. Remember: when you’ve finished a proof, try and ask yourself “have I covered all the possible cases?” and “have I proved everything I need to prove?”. In our example here, the first question means checking we’ve done all the infinitely many rationals, which we did. The second means checking the number we found was both rational and inbetween x and y, which it was.

If you have any questions, feel free to comment.

Good luck!

I’ve been given a request to go through a little bit on injective functions and to give a few examples. Unfortunately, my answer got a bit wordy, so I’ve split it in two. This is post is on injectivity, if you’d like a quick introduction to functions first, you can look back at the last post.

Injectivity

Remember to moral from our introduction to functions:

For a general function, it is possible for different elements to be sent to the same element.

With that in mind, we call a function f INJECTIVE if f always sends different elements to different elements. In our mathematically precise language, this comes out as

[a\neq b] \Longrightarrow [f(a)\neq f(b)],

though usually we prefer to write.

[f(a)=f(b)] \Longrightarrow [a=b].

  • Quick exercise: think about why the two statements above are the same.

When we looked at functions, we used the example

g:\mathbb{R}\to \mathbb{R}

a\mapsto a^2,

and we noticed that g(2)=4=g(-2), but certainly 2\neq -2 so this g is not injective. Now let’s think about the very similar looking function

\widetilde{g}: [0,\infty)\to \mathbb{R}

a \mapsto a^2.

The only thing we’ve changed here is the domain of the function, but this time, \widetilde{g} is injective, which is why we were so keen to stress that the domain is an important part of the definition of a function. Let’s just prove that \widetilde{g} is injective.

Suppose that \widetilde{g}(a) = \widetilde{g}(b) for some a and b in [0,\infty). This means that

a^2=b^2,

so  a= \pm b, but a and b are both in [0,\infty), so they are both positive or zero, so in fact a and b must be equal.

Now let’s look at a slightly more unusual example. Let’s define h to be

h:\mathbb{R} \to \mathbb{R}

h(x) = \begin{cases} x^2 & \text{if } x<0 \\ -x^2 & \text{if } x\ge 0\end{cases}.

Can you see straight away if this is injective or not?

If you want to prove it isn’t injective you just need to find one example of a pair of different elements which are sent to the same element, and that would be enough. If you want to prove it is injective, you need to show that if h(x)=h(y) then in fact x=y. Let’s try that and see what happens.

Suppose h(x)=h(y). Then either:

  1. x^2=y^2 and both x<0 and y<0.
  2. -x^2=-y^2 and both x\ge 0 and y \ge 0.
  3. x^2=-y^2 and x<0 and y\ge 0.

You might notice that I’ve missed out the case where y<0 and x\ge0, but hopefully you can see that 3 covers this just by switching the roles of x and y.

  • So, let’s start with case 1. If x^2=y^2, then x=\pm y, but x and y are both negative, so x=y.
  • Case 2 is only slightly more complicated. If -x^2=-y^2, then we can get rid of the minus signs to get x^2=y^2. Again, this gives x=\pm y, but x and y are both positive or zero, so in fact x=y.
  • Case 3 seems a little bit complicated. Think about the equation x^2=-y^2 for a minute. Remember that x and y are both real numbers, so x^2 and y^2 are both non-negative, and since x is strictly negative, x^2\neq 0. So in fact, case 3 can’t happen, because it says a positive number is equal to a negative number (or zero).

So overall, in all the cases that can actually happen, if h(x)=h(y) then x=y, which means h is indeed injective.

I hope this clears things up, and if you’re still having trouble, you can look here for some more explanations. If you want to see some more examples, feel free to write a comment, but do remember, I know what your homework questions are, so I won’t give away the answers to those.

 

Good luck!

I’ve been given a request to go through a little bit on injective functions and to give a few examples. Unfortunately, my answer got a bit wordy, so I’ve split it in two. This is a quick introduction to functions, if you’d prefer, you can skip straight on to the post on injectivity.

Functions

Firstly, let’s remind ourselves what a function is. Basically, a function is a machine which takes in one object (usually a number), and turns it into another object.

Diagram of a function

You’re used to functions like “adding 3”, “squaring” or trig functions like “\sin” and “\cos” , so you have the general idea about what we’re talking about, but in university maths we have to be more precise about exactly what a function is. For us, a function has 3 ingredients:

  1. A starting set, usually called the DOMAIN, or occasionally the SOURCE set. We’ll use the letter A for this space.
  2. A finishing set, usually the CO-DOMAIN, or sometimes the TARGET set. We’ll call it B.
  3. A rule for assigning one element of B to each element of A.

When describing a function f, we write

f:A\to B

a\mapsto f(a)

to describe it.

You might be used to thinking of functions just as the 3rd thing on the list, and maybe think that we’re being picky by saying that the starting set and finishing set are just as important. What we’re saying, for example, is that the “squaring” function going from \mathbb{R} to \mathbb{R} is different from the squaring function going from \mathbb{R}^+ (the positive reals) to \mathbb{R}. The idea of an injective function is a good example of why we’re so precise. Let’s quickly define a function to use as an example, we’ll use

g:\mathbb{R}\to \mathbb{R}

a\mapsto a^2.

An important thing to take from the definition of a function is that each thing in A only gets one thing from B, this is what we call the property of being WELL DEFINED. For something like the g we defined above, it means that when you square a real number, there’s only one possible answer: 2^2 = 4, and it will always be 4, no matter how many times you test it.

So, if I start with the same element, and apply the same function, I always end up with the same element, or to make it more mathematically precise:

[a=b] \Longrightarrow [f(a)=f(b)].

It’s important to notice, though, that if I finish with the same element, I need not have started with the same element. On our squaring function g, we have g(2) = 4 = g(-2), but 2  and -2 are certainly different. So the moral is:

For a general function, it is possible for different elements to be sent to the same element.

You’re now ready to learn about injectivity.

I got a question recently about solutions to complex number equations. By this, I don’t mean things like z+2=i, or similar, these you just solve as you would with a real number equation, I’m talking about equations that use the new tools you’ve got now we know about complex numbers, namely modulus (|\cdot|) and argument (\text{arg}). As with my last post, it tuns out that these sorts of equations are the sort of thing you almost certainly saw before (in disguise) at A-level: locus equations. In this post I’ll deal with the modulus, a future post will cover the argument.

You probably remember having to draw pictures of “all the points that are distance 3 from (2,1)” or “all the points which are twice as far from (2,4) as they are from (5,7)” . Think about what the modulus of a number is: it’s the distance of that number from 0 in the complex plane, so when we have an equation involving the modulus, it’s really asking you about the distance of a number from zero. Similarly, if we have some thing like |z - (2+3i)|, then that’s asking you about the distance of z from 2+3i.

WARNING! Remember that |z-(2+3i)| is not the same as |z-2+3i|. The first is the distance of z from 2+3i and the second is the distance of z from 2-3i, but it’s easy to miss this if you’re reading it quickly.

So let’s look at some examples. We’ll start slowly: what if I wanted to solve something like |z-i|=2? Recalling what we’ve just said, we get that this is describing all the points which are distance 2 from i, which I hope you will agree is a circle in the complex plane, radius 2, centre i. In particular, numbers like -i, 3i and i-2 are all on this circle. To get a proper equation for the curve, you can just remember what the modulus is in terms of a+bi. Then we get

|z-i| = \sqrt{(a+0)^2 + (b-1)^2}.

So if |z-i|=2, we get |z-i|^2=4, which gives us

a^2 +(b-1)^2=4.

Personally I’d leave the equation like this, but you might prefer to rearrange it a bit.

 

How about something a little harder. What about |z+i|+|z-i|=4? This is describing all the points which have the property that the sum of their distance from -i and their distance from i is 4. What does this look like? If you’ve got a good memory, or if you’ve reached this point in geometry already, you might know straight away, but if not, you could plot a few points on the curve and see what they look like. For starters, -2i is distance 1 from -i and distance 3 from i, so it’s on our curve, similarly 2i is on there. If you do the calculation, you can also see that \sqrt{3} and -\sqrt{3} are both distance 2 from each of the two points, so they are on the curve. If you play around a bit longer, you’ll start to sketch out an ellipse.

This time, doing it by equation is somewhat more long winded, but if you square both sides of

\sqrt{(a+0)^2 + (b+1)^2}+\sqrt{(a+0)^2+(b-1)^2} = 4

twice and preform some rearrangement, you can get it into the standard form of an ellipse. If you want to see the algebra, please write a comment, and I’ll post it, but I’d rather not confuse or scare you by clogging the page with calculations.

 

There are plenty of other ways to use the modulus to describe a curve, but hopefully I’ve given you a flavour for it here. Any queries: post a comment.

 

Good luck!

I’ve been asked about how to raise a complex number to a power, for example, what is (2+3i)^2. In fact, you’ve all learned how to do this before, but you might not have realised it at the time: this is exactly the same as taking (x+y)^2, and you will have come across this in both pure maths and statistics at A-level.

If you want to work out (2+3i)^2 you just look at it as (2+3i)(2+3i). From this we have

(2+3i)^2 = (2+3i)(2+3i)

= (2 \times 2) + (3i \times 2) + (2 \times 3i) + (3i \times 3i)

= 4 + 6i +6i + 9i^2

= 4 + 12i -9

= -5+12i .

If you want to work out (2+3i)^3, or higher powers you can either do it by hand as above, or use the binomial theorem, which you should have seen at A-level.

Taking very high powers

Of course, if you want to find some enormous power, like (2+3i)^{64}, even working it out using the binomial theorem could be a bit cumbersome. If you want to work out something like this, then you can notice things like the fact that (2+3i)^{64}=((2+3i)^2)^{32} or (2+3i)^{64}=((2+3i)^4)^{16} and so on. This works particularly well if some power of your number is real, because you know how to raise real numbers to powers very well.

For example, let’s look at (1+\sqrt{3}\cdot i)^{33}. By the binomial theorem,

(1+\sqrt{3}\cdot i)^3=1+3\sqrt{3}\cdot i+3(\sqrt{3}\cdot i)^2+(\sqrt{3}\cdot i)^3

=1+3\sqrt{3}\cdot i+3\cdot\sqrt{3}^2\cdot i^2+\sqrt{3}^3\cdot i^3

=1+3\sqrt{3}\cdot i -9 -3\sqrt{3}\cdot i

=-8,

so (1+\sqrt{3}\cdot i)^{33} = ((1+\sqrt{3}\cdot i)^3)^{11} = (-8)^{11}. Of course this is a very big number (it’s = -8589934592, as it happens!), but to get from (-8)^{11} to the final number, you don’t need any knowledge of complex numbers.

If you’re still a little unsure, the skills library have produced a few videos covering these ideas, they can be found here.

Good luck!

Welcome new students

Hello,

This is just a quick post to welcome new students studying MATH1035 (Analysis), and explain the purpose and procedure of this blog.

If you have a question about the lecture material that you want clarified or resolved, the first thing to do is to check that it hasn’t already been answered on this blog, you can do this be scrolling down through the previous posts. If your question hasn’t yet been answered yet, either email me on samuel@maths.leeds.ac.uk, or if you think you can do it in 140 characters, you’re welcome to tweet me on @sammaths. If you subscribe to this twitter feed, you will also get a tweet every time the blog is updated.

Feel free to comment on posts (remembering to be polite, of course), particularly if you have a follow up question (either to your question or someone elses), or if I didn’t quite explain what you wanted. Please also comment, again being polite, if you notice any mistakes in the entries, or if you have something to add. Remember, this is not a place to look for answers to homework. You’re welcome to ask your tutor or discuss homework problems amongst yourselves, but this is not the place for that discussion.

All in all, I hope this will be a valuable resource for analysis students, and subject to it being feasible, we may extend the remit next term. Your comments and constructive criticism are always appreciated.