Skip to content

Multiples in the Fibonacci series

Friday, May 9, 2008

I found the following problem on K. Rustan M. Leino’s puzzles page:

[Carroll Morgan told me this puzzle.]

Prove that for any positive K, every Kth number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.

More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) = 0, F(1) = 1, and F(n+2) = F(n+1) + F(n). Prove that for any positive K and natural n, F(n*K) is a multiple of F(K).

This problem caught my attention, because it looks like a good example for using a result that I have derived last year. My result gives a reasonable sufficient condition for showing that a function distributes over the greatest common divisor and shows that the Fibonacci function satisfies the condition.

In fact, using the property that the Fibonacci function distributes over the greatest common divisor, we can solve this problem very easily. Using \setms{0.1em}$\mathit{fib\/}{.}n$ to denote the Fibonacci number $n$, $m {\raisebox{0.5mm}{\ensuremath{\bigtriangledown}}} n$ to denote the greatest common divisor of $m$ and $n$, and $\setminus$ to denote the division relation, a possible proof is:

\begin{mpdisplay}{0.1em}{6.5mm}{2mm}{3}$\mathit{fib\/}{.}(n{\times}k)$ is a multiple of $\mathit{fib\/}{.}k$\push\-\\$=$ \> \>$\{$ \>\+\+\+definition\-\-$~~~ \}$\pop\\$\mathit{fib\/}{.}k\ms{1}{\setminus}\ms{1}\mathit{fib\/}{.}(n{\times}k)$\push\-\\$=$ \> \>$\{$ \>\+\+\+$\mathit{fib\/}{.}k$ divides $\mathit{fib\/}{.}(n{\times}k)$\-\-$~~~ \}$\pop\\$\mathit{fib\/}{.}k\ms{0}{\raisebox{0.5mm}{\ensuremath{\bigtriangledown}}} \ms{1}\mathit{fib\/}{.}(n{\times}k)\ms{1}{=}\ms{1}\mathit{fib\/}{.}k$\push\-\\$=$ \> \>$\{$ \>\+\+\+$\mathit{fib\/}$ distributes over $\raisebox{0.8mm}{\ensuremath{\bigtriangledown}}$\-\-$~~~ \}$\pop\\$\mathit{fib\/}{.}(k\ms{0}\raisebox{0.8mm}{\ensuremath{\bigtriangledown}} \ms{1}(n{\times}k))\ms{1}{=}\ms{1}\mathit{fib\/}{.}k$\push\-\\$=$ \> \>$\{$ \>\+\+\+$k\ms{0}\raisebox{0.8mm}{\ensuremath{\bigtriangledown}} \ms{1}(n{\times}k)\ms{1}{=}\ms{1}k$\-\-$~~~ \}$\pop\\$\mathit{fib\/}{.}k\ms{1}{=}\ms{1}\mathit{fib\/}{.}k$\push\-\\$=$ \> \>$\{$ \>\+\+\+reflexivity\-\-$~~~ \}$\pop\\$\mathit{true\/}~~.$\end{mpdisplay}

The crucial step is clearly the one where we apply the distributivity property. Distributivity properties are very important, because they allow us to rewrite expressions in a way that prioritizes the function that has the most relevant properties. In the example above we could not simplify $fib.k$ nor $fib.(n \times k)$, but applying the distributivity property prioritised the $\bigtriangledown$ operator — and we know how to simplify $k\ms{0}\raisebox{0.8mm}{\ensuremath{\bigtriangledown}} \ms{1}(n{\times}k)$. Furthermore, in practice, distributivity properties reduce to simple syntactic manipulations, thus reducing the introduction of error and simplifying the verification of our arguments.

(Now that I think about it, perhaps it would be a good idea to write a note on distributivity properties, summarizing their importance and their relation with symbol dynamics.)

If you have any corrections, questions, or alternative proofs, please leave a comment!

Filed in Mathematics, Methodology | Comments (4)

New domain name (joaoff.com)

Monday, February 25, 2008

Some people were complaining about the domain joaoferreira.org, because it was a bit long and they never got the number of r’s in Ferreira right. From today, they can’t complain anymore!

The new and official URL of this website is now shorter and r’s-free: joaoff.com .

If you don’t like it and prefer the old one, please let me know!

Filed in Personal | Comments (2)

A reward check from Donald Knuth

Monday, February 25, 2008

The other day I went to my pigeon-hole to collect my snail mail, and I had a letter from Donald E. Knuth, Professor Emeritus of the Art of Computer Programming!

Cover of the letter that Knuth sent to Joao

Inside, there was a check for a correction I sent him some months ago. In fact, it was not really a correction; it was more like a comment. And it was so obvious (he even said that) that he just sent $0.32, instead of the usual $2.56. But hey, who cares? I’ve got Knuth’s autograph now :-)

A reward check from Donald Knuth

Perhaps I should set as one of my goals to find a proper error, so that I can receive a $2.56 check :) By the way, the errata of the Concrete Mathematics is available online and this particular omission is documented as follows:

page 338, line 2 from the bottom
   change “for $z$” to “for $z$ and multiplying by $a$”

Filed in Personal | Comments (2)

Calculational proofs are usually direct

Monday, February 11, 2008

jd2718 asked in his blog if anyone knew a direct proof of the irrationality of $\sqrt 2$  . In this post I present a proof that, even if some don’t consider it direct, is a nice example of the effectiveness of calculational proof. But first, there are two concepts that need to be clarified: direct proof and irrational number.

Direct proofs

The concept of direct proof can vary slightly from person to person. For instance, Wikipedia defines it as:

In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions.

Alternatively, in Larry W. Cusick’s website we can read:

A direct poof [sic] should be thought of as a flow of implications beginning with “P” and ending with “Q”.

P -> … -> Q

Most proofs are (and should be) direct proofs. Always try direct proof first, unless you have a good reason not to.

I consider the wording ‘without making any further assumptions‘ in the first definition ambiguous and I don’t understand why the second definition only applies to implications. But anyway, with these definitions in mind, a direct proof for the irrationality of $\sqrt{2}$ can be something like:

\setms{0.1em}\begin{mpdisplay}{0.1em}{8.5mm}{2mm}{3}$\sqrt{2}$ is irrational\push\-\\$=$ \> \>$\{$ \>\+\+\+justification\-\-$~~~ \}$\pop\\$\mathit{true\/}~~.$\end{mpdisplay}

Or, alternatively, we can also use a proof of the following shape:

\begin{mpdisplay}{0.1em}{8.5mm}{2mm}{3}$\sqrt{2}$ is irrational\push\-\\$\Leftarrow$ \> \>$\{$ \>\+\+\+justification\-\-$~~~ \}$\pop\\$\mathit{true\/}~~.$\end{mpdisplay}

Irrational numbers

An irrational number is a real number that can’t be expressed as a simple fraction. Therefore, the number $\sqrt{2}$ is irrational because for all integers m and n, with n non-negative, we have that:

\begin{displaymath}\sqrt{2}\ms{2}~~{\neq}~~\ms{2}{\displaystyle\frac{m}{n}}\mbox{\ \ \ .}\end{displaymath}

A direct proof for the irrationality of $\sqrt{2}$

Now that we have clarified the concepts above, we prove that $\sqrt{2}$ is irrational. For all integers m and n, with n non-negative, we have:

\begin{mpdisplay}{0.1em}{8.5mm}{2mm}{3}$\sqrt{2}\ms{1}~{\neq}~\ms{1}{\displaystyle\frac{m}{n}}$\push\-\\$=$ \> \>$\{$ \>\+\+\+Use arithmetic to eliminate the square root operator.\-\-$~~~ \}$\pop\\$n^{2}{\times}2\ms{1}~{\neq}~\ms{1}m^{2}$\push\-\\$\Leftarrow$ \> \>$\{$ \>\+\+\+Two values are different if applying the same function to them\\ yields different values.\-\-$~~~ \}$\pop\\$\mathit{exp\/}{.}(n^{2}{\times}2)\ms{1}~{\neq}~\ms{1}\mathit{exp\/}{.}m^{2}$\push\-\\$=$ \> \>$\{$ \>\+\+\+Now we choose the function $exp.$\\Let $\mathit{exp\/}{.}k$ be the number that $2$ divides $k.$\\The function $\mathit{exp\/}$ has two important properties:\\~~~$\mathit{exp\/}{.}2\ms{1}{=}\ms{1}1$ and\\~~~$\mathit{exp\/}{.}(k{\times}l)\ms{2}{=}\ms{2}\mathit{exp\/}{.}k\ms{2}{+}\ms{2}\mathit{exp\/}{.}l$ .\\We apply these properties to simplify the left and right sides.\-\-$~~~ \}$\pop\\$1\ms{2}{+}\ms{2}2\ms{1}{\times}\ms{1}\mathit{exp\/}{.}n\ms{3}~{\neq}~\ms{3}2\ms{1}{\times}\ms{1}\mathit{exp\/}{.}m$\push\-\\ $=$ \> \>$\{$ \>\+\+\+The left side is an odd number and the right side is an even\\ number. Odd numbers and even numbers are different.\-\-$~~~ \}$\pop\\$\mathit{true\/}~~.$\end{mpdisplay}

Note that, unlike traditional proofs, we don’t assume that m and n are co-prime, nor that $\sqrt{2}$ is a rational. We essentially derive the boolean value of the expression $\sqrt{2}\ms{2}~~{\neq}~~\ms{2}{\displaystyle\frac{m}{n}}\mbox{\ \ \ .}$

If you have any suggestions or corrections, please leave a comment. I’d be more than happy to hear from you.

Note: I learnt the contrapositive of this proof from Roland Backhouse (page 38, Program Construction — Calculating Implementations from Specifications).

Filed in Education, Mathematics | Comments (8)

In Defense Of Computer Science

Wednesday, January 30, 2008

Very good post from Paper Trail:

So why study computer science? The job prospects at the end are usually pretty good - because, if nothing else, you can become a pretty good software developer fairly quickly - but they are unknown. My argument is that the study of computer science is enough of an incentive enough to make it worthwhile.

Related Articles:

Filed in Education, Programming | Comments (0)

The programmers of tomorrow

Tuesday, January 22, 2008

A recent article written by Dr. Robert B.K. Dewar and Dr. Edmond Schonberg (both from AdaCore Inc.) is generating some discussion on the state of Computer Science (CS) education in the United States. In “Computer Science Education: Where Are the Software Engineers of Tomorrow?“, Dewar and Schonberg claim that U.S. universities are training unqualified and easily replaceable programmers.

“It is our view that Computer Science (CS) education is neglecting basic skills, in particular in the areas of programming and formal methods. We consider that the general adoption of Java as a first programming language is in part responsible for this decline. We examine briefly the set of programming skills that should be part of every software professional’s repertoire.”

The comment about Java’s adoption annoyed some Java aficionados, but in a recent interview, Robert Dewar adds that the problem goes far beyond the choice of Java as the first programming language. The real problem is that CS programs are being dumbed down, so that they become more accessible and popular. In result, they “are not rigorous enough and don’t promote in-depth thinking and problem solving”.

“A lot of it is, ‘Let’s make this all more fun.’ You know, ‘Math is not fun, let’s reduce math requirements. Algorithms are not fun, let’s get rid of them. Ewww – graphic libraries, they’re fun. Let’s have people mess with libraries. And [forget] all this business about ‘command line’ – we’ll have people use nice visual interfaces where they can point and click and do fancy graphic stuff and have fun.”

Although the paper is concerned with the American reality, I believe we have the same problem in Europe — at least, and as far as I know, in the UK and in Portugal. However, in my opinion, the problem starts before university. The maths’s programs in secondary schools are also being simplified (or dumbed down, if you prefer) and many important concepts, like logic and proofs, are being ignored.

In result, first-year students usually have a poor background on maths and problem solving. In fact, most of them have never seen a proof and don’t even understand the importance of mathematical reasoning. With poor reasoning abilities, they become intellectually less curious, accepting things as they are presented, and they have tremendous difficulties creating new algorithms, or convincing someone that their own algorithms are correct.

Moreover, once they are in the university, one of two things happens:

  1. they are not taught explicitly how to solve problems or how to derive algorithms from their formal specifications (this is the most common case);
  2. or they are taught the above skills but their poor background doesn’t allow them to fully appreciate these subjects.

(Continued)

Related Articles:

Filed in Algorithms, Education, Mathematics, Methodology, Opinion, Programming | Comments (13)

A square grid path problem

Sunday, January 20, 2008

Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.

Problem statement

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

Path diagram for 4×4 square grid

How many routes are there through a 20×20 grid?

My solution

In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in a n×n grid. Our argument is based on three observations:

  1. all the paths have size 2×n (the reason is obvious: you have to go right n positions and down another n positions);
  2. since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
  3. the strings mentioned above must contain the same number of Rs and Ds.

From these three observations, we can transform the problem to the following:

How many different strings of size 2×n, consisting of n Rs and n Ds, there are?

The solution is now very simple, because the positioning of n Ds (or Rs) determines the positioning of the other n Rs (or Ds). Hence, the number we are interested in is the number in which we can choose n positions from 2×n available. The answer, using the traditional notation for the binomial coefficient, is:

$${2n \choose n} = \frac{(2n)!}{n!\times n!}~~~~.$$

Instantiating n with 20, we get the answer to the initial problem of the 20×20 grid.

Generalization to m×n grids

The generalization to a m×n grid is also simple. The only difference is that the strings have length m+n. Using the same reasoning as above, the number of paths through a m×n grid is:

$${m+n \choose n} = \frac{(m+n)!}{m!\times n!}~~~~.$$

Final note: If you want to access the forum of the problem, you have to solve it.

Filed in Algorithms, Mathematics | Comments (10)

How to be more confident about your own programs: an example using Perl

Thursday, July 26, 2007

Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.

Perl Camel

It was Edsger W. Dijkstra, the famous computer scientist, who wrote these words in his note named “How do we tell truths that might hurt?“. I am sure that many people didn’t like to read them, and didn’t understand what he meant.

Although it is not my intention to discuss his words, I want to present a simple example that demonstrates how mathematics can be used to program better and to make you more confident about your own programs.

This post includes a fair amount of mathematical definitions and concepts, but they should not be difficult to understand. After the mathematical discussion, I present an example using the Perl programming language (it also applies to languages like C or Java).

The Problem

The problem I am going to deal with, involves the ceiling and floor functions. If you don’t remember, the floor of a real number $x$ is (usually) written as $\left\lfloor{}x\right\rfloor$ and it is defined as the greatest integer that is at most $x$. Similarly, the ceiling of a real number $x$ is written as $\left\lceil{}x\right\rceil$ and it is defined as the smallest integer that is at least $x$.

The goal is to implement the ceiling function supposing that our programming language only provides the floor function to round numbers. Formally, given a real $x$, we want to calculate an expression $e$ such that:

\begin{displaymath}\setms{0.2em}\left\lceil{}x\right\rceil\ms{1}{=}\ms{1}\left\lfloor{}e\right\rfloor\mbox{\ \ \ .}\end{displaymath}

(Continued)

Related Articles:

Filed in Algorithms, Mathematics, Perl, Programming | Comments (3)

Swapping the values of two variables

Wednesday, July 11, 2007

In my previous post I have promised that I would put here some of my technical notes (JFFs). Today I am posting JFF1, which presents a very well-known problem in a non-traditional way. The problem is how to swap the values of two variables without using another temporary one.

I start by presenting the properties involved in the traditional solution and then I generalize it for arbitrary operators. I finish the note with a simple refinement. If you have any nice example instantiation for the last set of assumptions, I would be glad to know it. Other than that, comments or corrections are more than welcome!
The note is available in PDF. Click the following link to get it:

JFF1 - Swapping the value of two variables

Related Articles:

Filed in Algorithms, Mathematics, Programming | Comments (2)

I am still alive!

Friday, June 15, 2007

That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.

A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.

Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.

(Continued)

Filed in Algorithms, Mathematics, Personal, Programming | Comments (0)