The big overlap between mathematics and programming is proof by mathematical induction. The standard example in mathematics is proving that 1+2+...+n = n(n+1)/

The big overlap between mathematics and programming is proof by mathematical induction. The standard example in mathematics is proving that 1+2+...+n = n(n+1)/2 The proof has two parts, first is it true for small values of n, and second does truth for a large value follow from truth for all small values. Well, 1+2+3 = 6 and 3x(3+1)/2 = 6, so small n is looking good. What about general n? Can we get the formula for n from the formula for earlier n, perhaps n-1? Suppose we already knew 1+2+...+(n-1) = (n-1)((n-1)+1)/2 = n(n-1)/2. Adding n to n(n-1)/2 does indeed produce n(n+1)/2 so gives us the second part and completes the proof. The standard example in programming is writing a fast sorting routine. Given data x1,x2,...,xn pick one item, perhaps x1, as the pivot and work through the data accumulating two lists, big and little, of data larger than and smaller than the pivot. Join the sorted versions of big and little with the pivot in between. The algorithm works because it works for small n as special cases and works for larger n by breaking the big case into smaller subcases. A list with only one item is inherently sorted and a list with exactly two items is easily sorted by swapping them if needed. A list with n items gets broken into a pivot and two lists big and little. Both lists are less than n long. Even in the lopsided case that one is empty the other is only n-1 long because we have taken out the pivot. So the sorting routine is going to work because it works for smaller cases, by just the same logic that underlies mathematical induction. School mathematics has a misleading focus on computation. University mathematics is focused on proof. In programming we tend to keep the proofs in our heads and not write them down. The reason for this is that computers need a great deal of handholding and babysitting. A computer program is mostly made of details that spell things out for the computer in detail. These details are typically mathematically shallow. Provided we have not made any small slips with the details the program will work and obviously so. On the other hand, interesting programs have tricky bits that are not mathematically shallow. How do you write those? You need to think like a mathematician writing a proof. You need to find bases cases and inductive steps. Mathematics and programming are different but mutually illuminating. There is a very close connection between a mathematic proof and the explanation of why a tricky computer program works. Learning how to create mathematical proofs will help you with writing tricky programs and vice-versa. The most important example is calculus. Many mathematics students struggle with calculus. It is a useful exercise (perhaps for 16 to 18 year olds) to write your own computer programs for numerical differentiation and for symbolic differentiation and to get the two to agree as closely as rounding error permits. Much that is obscure about calculus then becomes clear. The overlap of mathematics and programming is very clear in formalisms such as ACL2 http://www.cs.utexas.edu/users/moore/acl2/ http://www.cs.utexas.edu/users/moore/acl2/ which use a computer programming language as a logic in which mathematical theorems are stated and proven. The ACL2 book is excellent, but alas, it assumes a university level grasp of meta-mathematics. I fear that the book the poster seeks has yet to be written. Perhaps some-one on HN will take up the challenge?