venerdì, maggio 31, 2013

Test-driven maths: convergent sequences

I want to show today that working in the paradigm of test-driven-development, we can develop a working definition of a convergent sequence. Metaphorically speaking, we want to develop a mathematical "program" that, given a sequence, says to us that this sequence is convergent in some useful sense.

I will start with an easy example (which will be our first test). We look at the sequence of numbers, which we will call

Test sequence 1

$$1, \frac{1}{2},  \frac{1}{3},  \frac{1}{4}, ...$$

or, in other, terms $\{\frac{1}{n}\}_n$

It is clear (by intuition) that the numbers in this sequence (in the following sequence 1) become smaller and smaller approaching, but never touching 0. For this reason we will use this as our first test case, and try to derive a formal definition of what is a sequence of numbers that converges to 0.

By looking at the sequence 2 things become apparent: 1) the numbers get smaller and smaller and 2) the  numbers always are positive. So we try our first defintion.

Convergent sequences, take 1

A sequence of positive numbers is said to be convergent to 0 if the numbers become smaller and smaller.

Let us try now to put it in more formal terms


Convergent sequences, take 2

A sequence of positive numbers $x_n\geq0$ is said to be convergent to 0 if $x_{n+1}< x_n$ for all $n$ index of the sequence.

Since now $\frac{1}{n+1}<\frac{1}{n}$, this definition seems to include our test tesequence 1, in the sense that according to this definition, our sequence converges to 0. Can we stop now? No. We have written a small test (checking whether the sequence 1 is converging) and a small piece of code (our take 2). But our mathematical insight is not yet satisfied, because our test does not cover many possible inputs (in form of test sequences of course). So, we have to extend our test.

In particular, it is maybe useful to have a sequence of which we know (always by intuition) that it does not converge to 0 so that we can check that our definition also fails when it must. The simplest thing to do is to consider the sequence 1 and add 1 to all members.


Test sequence 2

$$2, 1+\frac{1}{2},  1+\frac{1}{3},  1+\frac{1}{4}, ...$$

Now, since our sequence is composed of decreasing positive numbers, our tentative definition would call it convergent. Since we know that this sequence does not converge, that means that our program (take 2) does not pass the test. In fact the point is that our test sequence 2 is always at least 1 away from 0. So, let us add to our definition that the sequence cannot have a definite distance from 0.

Convergent sequences, take 3

A sequence of positive numbers $x_n\geq0$ is said to be convergent to 0 if $x_{n+1}< x_n$ for all $n$ index of the sequence and for any positive number $\epsilon$, it is not true that all numbers in the sequence are larger than $\epsilon$.

This looks good. Let us build some new test to check whether we are really there. Say, we take the sequence 2 and we put some 0 here and there. The resulting sequence should not converge according to our definition, since we are not getting closer and closer to 0 with all numbers!


Test sequence 3

$$2, 0, 1+\frac{1}{2},  0, 1+\frac{1}{3},  0, 1+\frac{1}{4}, ...$$

Now we have problem. The sequence is clearly non convergent: if we take the odd indexes, we go to 1, otherwise we go to 0. Since we have 0s over and over again in our sequence, we cannot find an $\epsilon$ such that all numbers are larger than that, so for that reason the sequence would be classified as convergent. But: since we inserted 0 over and over again, the numbers are not decreasing, and the sequence is classified as not convergent for that reason. This sounds weird. It looks that we pass the test, but for the wrong reason. Let us keep in mind that there is some problem with the decreasing property and let us correct the part regarding the distance from 0.


Convergent sequences, take 4

A sequence of positive numbers $x_n\geq0$ is said to be convergent to 0 if $x_{n+1}< x_n$ for all $n$ index of the sequence and for any positive number $\epsilon$, we can find some index $k$ (dependent on $\epsilon$) such that all numbers with index larger than $k$ are smaller than $\epsilon$.

Now we are on the safer side with the test sequences 2 and 3. Indeed, if I choose my $\epsilon = 0.9$ I am not able to find any index such that the numbers with larger index are smaller than 0.9, since I have over and over again some $1+\frac{1}{n}$ popping up in my sequence. Are we still on the safe side with sequence 1? Yes, since if I choose $k=\frac{1}{\epsilon}$, it is clear that for all larger index the numbers in the sequence are smaller than $\epsilon$ (this is undergraduate algebra, just try it). Note that now the test sequence 3 is classified as not convergent for both not being decreasing and for being not arbitrary small.

Now let us go back to the problem with the decreasing sequences.. If I have a sequence of numbers and scramble the order, I do not want that this scrambling changes whether we call the sequence convergent or not. So, we come with a second test sequences that has to converge.


Test sequence 4

$$\frac{1}{2},  1,  \frac{1}{4}, \frac{1}{3}, ...$$

We just switched the position of the neighbours. Now, this sequence is intuitevly convergent, but our take 4 says it is not, since the elements are not decreasing. So, what if we drop the assumption of having decreasing numbers?


Convergent sequences, take 5

A sequence of positive numbers $x_n\geq0$ is said to be convergent to 0 if for any positive number $\epsilon$, we can find some index $k$ (dependent on $\epsilon$) such that all numbers with index larger than $k$ are smaller than $\epsilon$.

This sounds familiar. Surprising as it is, real world mathematics really feel like that often: you start with some hypothesis of a theorem, try out some examples, until you are confident enough. Constructing the examples exactly gives you the boundaries of the hypothetical theorem. Can we build proofs by this method?

A test-driven revival

Since more than 1 year I left Freiburg and the BCF to start working in the development of MEMS with Bosch GmbH. For some complicated reasons connected to my work there, I've got involved in software engineering and in particular in test-driven development. But only today I realised why I've got involved there and why I like it.

In fact, test-driven development is a kind of "formalization" of how mathematicians actually work!

In particular, I found it complying with Gower's pedagogical principle.

Following this intuition, I will try in the next days (months?) to revive this blog, and to show that what computer scientists rediscovered in the middle of the of 90ies as test-driven development is nothing but what mathematicians are doing since centuries.