Skip to content

Tag Archives: calculational

Probabilities in Proofreading

Monday, September 14, 2009

Suppose you write a program and you send the source code to two of your friends, and . Your two friends read the code and when they finish, A errors are detected by , B errors are detected by , and C errors are detected by both. So, in total, A+B-C errors are detected [...]

Filed in Algorithms, Computing Science, Education, Mathematics, Programming, Science | Also tagged , , , , , , , , , , | Comments (2)

A Calculational Proof of the Handshaking Lemma

Tuesday, April 7, 2009

In graph theory, the degree of a vertex A, d.A, is the number of edges incident with the vertex A, counting loops twice. So, considering graph 0 below, we have d.A=3, d.B=3, d.C=1, d.D=3, and d.E=2.
A well-known property is that every undirected graph contains an even number of vertices with odd degree. The result first [...]

Filed in Algorithms, Computing Science, Education, Mathematics, Methodology | Also tagged , , , , , , , , | Comments (2)

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) [...]

Filed in Mathematics, Methodology | Also tagged , , , | Comments (6)

Calculational proofs are usually direct

Monday, February 11, 2008

jd2718 asked in his blog if anyone knew a direct proof of the irrationality of   . 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 [...]

Filed in Education, Mathematics | Also tagged , , , | Comments (14)