Fibonacci multiples

Posted on May 15, 2012 by

I haven’t written anything here in a while, but hope to write more regularly now that the semester is over—I have a series on combinatorial proofs to finish up, some books to review, and a few other things planned. But to ease back into things, here’s a little puzzle for you. Recall that the Fibonacci numbers are defined by

F_0 = 0; F_1 = 1; F_{n+2} = F_{n+1} + F_n.

Can you figure out a way to prove the following cute theorem?

If m evenly divides n, then F_m evenly divides F_n.

(Incidentally, the existence of this theorem constitutes good evidence that the “correct” definition of F_0 is 0, not 1.)

For example, 5 evenly divides 10, and sure enough, F_5 = 5 evenly divides F_{10} = 55. 13 evenly divides 91, and sure enough, F_{13} = 233 evenly divides F_{91} = 4660046610375530309 (in particular, 4660046610375530309 = 233 \times 20000200044530173).

I know of two different ways to prove it; there are probably more! Neither of the proofs I know is particularly obvious, but they do not require any difficult concepts.

Posted in arithmetic, challenges, fibonacci, number theory, pattern | Tagged , | 9 Comments

Carnival of Mathematics 86

Posted on May 8, 2012 by
Carnival of Mathematics logo

Welcome to the 86th Carnival of Mathematics! 86 = 2 \cdot 43 = 222_6 = 20+21+22+23 = 3^2 + 4^2 + 5^2 + 6^2 is semiprime, nontotient, and noncototient. It is also happy since 8^2 + 6^2 = 64 + 36 = 100 and 1^2 + 0^2 + 0^2 = 1. In fact, it is the smallest happy, nontotient semiprime (the only smaller happy nontotient is 68—which is, of course, 86 in reverse—but 68 is not semiprime).

However, the most interesting mathematical fact about 86 (in my opinion) is that it is the largest known integer n for which the decimal expansion of 2^n contains no zeros! In particular, 2^{86} = 77371252455336267181195264. Although no one has proved it is the largest such n, every 2^n up to n = 4.6 \times 10^7 (which is quite a lot, although still slightly less than the total number of integers) has been checked to contain at least one zero. The probability that any larger power of 2 contains no zeros is vanishingly small, given some reasonable assumptions about the distribution of digits in base-ten expansions of powers of two.

“Eighty-six” is also apparently some sort of slang term in American English, but it really has nothing to do with math, so who cares? Onward to the carnival! I had a lot of fun reading all the submissions, and have decided to organize them somewhat thematically—though they don’t always fit perfectly, so don’t assume you won’t be interested in a post just because of my categorization!

Art

Money polyhedron

Christian Perfect has started a series of posts on the theme of “Arty Maths”, with links to artistic images and videos with a mathematical bent. Above is a cool example, some sort of stellated polyhedron made out of money by Kristi Malakoff (you can find more here).

Katie Steckles submitted a link to Robby Ingebretsen’s blog post First Digital 3D Rendered Film (from 1972) and My Visit to Pixar. Katie says,

This is possibly the earliest example of a computer animation, and one of its two creators, Edwin Catmull, who went on to found Pixar, is credited with “having work[ed] out [the] math to handle things like texture mapping, 3D anti-aliasing and z-buffering”. Fascinating to think he had to invent all of that in order to do this!

Robby’s blog post (and the extensive comments on it) give a lot more context and fascinating details. And, of course, you can watch the video itself!

Mike Croucher of Walking Randomly writes about some cool mathematically-themed stained glass windows, and wonders whether anyone knows of any others.

Statistics/data analysis

Arthur Charpentier of Freakonometrics writes about Nonconvexity, and playing indoor paintball: if a bunch of people in a nonconvex playing area are all holding water pistols and shoot at the closest person, who doesn’t get wet?

Katie Steckles submitted a link to Data: it’s how stores know you’re pregnant, an article by Matthew Lane of Math Goes Pop! Ever wonder how companies can predict various things about you (such as whether you are pregnant!) based on your browsing habits and other publicly available data? This article explains some of the basic math underlying this sort of “data mining”.

John Cook of The Endeavour answers the question: What is randomness? in Random is as random does. It turns out that the best answer might just be to avoid answering at all!

Geometry

Augustus Van Dusen of thinkingmachineblog submitted a post titled Superellipse, saying

I read an article about Sergels torg, a plaza in Stockholm, being an example of a superellipse. When I looked up superellipse on Wolfram math world, I noticed that the area formula involved gamma functions. I then decided to derive the result myself to see if it could be simplified and how it would reduce to the familiar formula for the area of an ellipse.

Frederick Koh of White Group Mathematics shares a geometric solution to an optimization problem that doesn’t initially seem like it has anything to do with geometry.

Zachary Abel of Three-Cornered Things has written a series of three “excursions into the miraculous and interconnected workings of the humble triangle”: Many Morley Triangles, Several Sneaky Circles, and Three-Cornered Deltoids. These are some of my personal favorites from this month’s Carnival: chock-full of surprising mathematics and beautiful illustrations and animations!

Teaching

Colin Wright writes The Trapezium Conundrum: how should a trapezium (aka trapezoid if you’re from the US) be defined—with exactly one pair of parallel sides or at least one pair of parallel sides? More generally, how are definitions arrived at and agreed upon? The answer may depend on the audience.

Karen G. of school•a•rama muses upon the relationship between language and learning place value in her post Looking to Asia.

On her blog Math Mama Writes…, Sue VanHattum writes about Linear Algebra: Leading into the Eigen Stuff. Sue says, “I’m teaching linear algebra for the first time in over a decade. That has meant relearning it—a delightful experience.”

Paul Salomon of Lost In Recursion writes Exponents and the Scale of the Universe – a 21st Century math lesson, a fun story about how an initially dry lesson on exponents turned into a remarkable learning experience.

Fun

Alistair Bird submitted a link to Enormous Integers, saying,

It’s still a common enough misconception that pure mathematics research must be about larger and larger numbers, but it’s still nice to sometimes play up to this stereotype, as John Baez’s blogpost on Azimuth about ‘Enormous Integers’ does. Comments are worth a look too.

Pat Ballew writes on Pat’sBlog about Pandigital Primes: “exploring pandigital primes and finding out how handy Computer programming skills might be”.

Quick, what comes next in the series \pi/2, \pi/2, \pi/2, \pi/2, \pi/2, \pi/2, \pi/2, \dots? The answer, as explained by Steven Landsburg on his blog, The Big Questions, may surprise you! (Thanks to Katie Steckles for the submission, via Alexandre Borovik.)

Paul Salomon of Lost In Recursion displays The “Lost in Recursion” Recursion. Can you figure out what’s going on without getting lost in the “The ‘Lost in Recursion’ Recursion” recursion?

Stuff That Did Not Fit In Any Other Category But Is Still Awesome

Colin Beveridge of Flying Colours Maths submitted Secrets of the Mathematical Ninja: The surprising integration rule you don’t get taught in school, and writes,

When I stumbled across this rule, my reaction was ‘whoa.’ It’s quick, it’s extremely dirty, and it’s surprisingly accurate. The kind of thing the mathematical ninja dreams of.

Andrew Taylor writes a guest post, Electoral Reforms and Non-Transitive Dice, on The Aperiodical, explaining Why Choosing a Voting System is Hard in terms of a set of nontransitive dice.

Peter Rowlett, of Travels in a Mathematical World, opines in his post, What a nice job you have, that a popular ranking listing “mathematician” as one of the top ten best jobs shouldn’t just be accepted and repeated uncritically.

In her article How culture shaped a mathematician, Carol Clark gives a glimpse into the life and background of mathematician Skip Garibaldi. She writes:

Mathematicians see the world differently than me. I interviewed a mathematician to get a glimpse of that view, and learned how everything from fine art to popular films and books played a role in shaping that view.

The previous Carnival of Mathematics was hosted at Travels in a Mathematical World; next month, the 87th Carnival will be hosted by Mr. Chase at Random Walks, so start getting your submissions ready now! For lists of past and future carnivals, instructions on submitting, and answers to frequently asked questions, see the main Carnival of Mathematics site. The next Math Teachers at Play carnival is also coming up soon, with a submission deadline of this Friday.

Posted in links | Tagged | 1 Comment

I’ll be hosting the Carnival of Mathematics, and the submission deadline is coming up soon—Tuesday, May 1. Please submit something! It could be something you wrote, or something someone else wrote that you enjoyed. All mathematics ranging from elementary to advanced is welcome.

Posted on April 23, 2012 by | Leave a comment

Book review: In Pursuit of the Traveling Salesman

Posted on April 7, 2012 by

As mathematical problems go, the “traveling salesman problem” (TSP) is a rare gem: it is simultaneously of great theoretical, historical, and practical interest. On the theoretical front, it is a well-known example of the class of “NP-complete” problems, which lie at the heart of the million-dollar “P vs NP” question (which I still intend to explain at some point). Historically, it has been studied for almost 200 years (given a sufficiently inclusive definition of “study”), and has occupied a place in the public consciousness for at least the last 50. And this great historical interest is partly due to the problem’s practical significance.

So, what is it? Given a set of points in the plane (or, more generally, a set of points with “distances” specified somehow between each pair of points), the problem is to determine the shortest path which visits every point exactly once and then returns to the starting location. Of course, in one sense this is “easy”: just list all possible paths and compute the length of each. Note, however, that for a set of n points, there are (n-1)! (that is, 1 \cdot 2 \cdot 3 \cdot \dots \cdot (n-1)) possible paths that visit every point once and then return to the start. Even with only 30 points, that’s a whopping 8841761993739701954543616000000 possible paths—if you could compute the length of one trillion paths every second, it would still take 280 million millenia (that’s 2.8 \times 10^{11} years, slightly longer than I’ve been alive) to check all of them! And that’s only 30 points—in practice, people want to solve the TSP for sets of points much larger than 30. So the point is not just to “solve” the problem; the real question is, can it be solved efficiently?

Amazingly, no one knows! But that hasn’t stopped people from coming up with extremely clever algorithms that seem to work well in practice, on very large sets of points (i.e. thousands, or even tens of thousands of points)—even though there are “pathological” inputs for which these algorithms do essentially no better than just trying every path. So these algorithms constitute a good solution to the TSP from a practical point of view but not a theoretical one!

William Cook’s new book, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, does a wonderful job presenting the history and significance of the TSP and an overview of cutting-edge research. It’s a beautiful, visually rich book, full of color photographs and diagrams that enliven both the narrative and mathematical presentation. And it includes a wealth of information (perhaps even a bit too much at times; I got lost in a few places). But it actually bills itself, partly, as an introduction to cutting-edge ideas in TSP research—and I think overall it succeeds admirably, explaining ideas in ways that are accessible but not patronizing. Read this book if you want a fun, beautifully illustrated introduction to (this one fascinating piece of) the edge of human knowledge!

Posted in books, computation, geometry, open problems, review | Tagged , , | 6 Comments

New Carnival of Mathematics

Posted on April 5, 2012 by

The Carnival of Mathematics has been revived! A big thanks to Mike Croucher of Walking Randomly for organizing it for the past few years, and to Katie Steckles, Christian Perfect, and Peter Rowlett for taking over. The latest edition, carnival #85 (wow, has it really been going that long?) is now up at Peter Rowlett’s blog, Travels in a Mathematical World. Lots of cool stuff there, so be sure to check it out if you haven’t already.

I’ll be hosting Carnival #86 here, so please submit something! The deadline is May 1st, and I’ll post the carnival sometime the week after that.

Posted in links, meta | Tagged | Leave a comment

Making our equation count

Posted on March 3, 2012 by

[This is post #4 in a series; previous posts can be found here: Differences of powers of consecutive integers, Differences of powers of consecutive integers, part II, Combinatorial proofs.]

We’re still trying to find a proof of the equation

\displaystyle \sum_{i=0}^n (-1)^{n-i} \binom n i (k+i)^n = n!

which expresses the fact that a certain arithmetic procedure always seems to result, strangely enough, in the factorial of n. Last time I introduced the idea of using a combinatorial proof, and gave a simple example involving a binomial coefficient identity.

In order for this idea to yield any fruit, we need a way to interpret the various pieces of the equation as counting something. Let’s go over the pieces one by one and discuss some ways to interpret them combinatorially.

Factorial, permutations, and matchings

Let’s start with the right-hand side, n!. This one is not too hard: n! counts the number of permutations of n objects, that is, the number of different ways to take n distinct objects and arrange them in an ordered list. Why is that? Well, there are n objects we could choose to put first; once we’ve made that choice, there are n-1 remaining objects we could choose to go second; then n-2 choices for the third object, and so on, for a total of n (n-1) (n-2) \dots 1 = n! choices. For example, here are the 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 different permutations of size 4:

However, there’s another way to think about permutations which will come in handy later. Namely, we can think of a permutation as a matching between two sets of size n. You know, like those puzzles that give two side-by-side lists and say “draw a line matching each cartoon character with their favorite cheese!” (…or whatever). Like this:

Here we have a matching between two sets of size 6. Each dot on the left is matched with exactly one dot on the right, and vice versa.

Why are matchings another way of thinking about permutations? First, it’s not too hard to see that there are also n! matchings between two sets of size n: we have n possible choices of what to match the first element with; then there are n-1 choices left over for what to match the second element with, and so on.

But we can also see a correspondence between permutations and matchings more directly. Start by labeling the dots on the left of a matching with consecutive numbers:

Now, imagine each number “traveling” along the corresponding red edge until it reaches the dot on the other side. Like this:

See how the 1 traveled down the steep edge to end up at the fourth dot from the top; the 2 traveled across the horizontal edge to stay in the same position; the 3 traveled up to the top; and so on.

What we get out is a list of the numbers from 1–6 in some order; in this example we get 3,2,5,1,6,4. In other words, we can view a matching as a little physical machine for taking a list of objects and putting them into some particular order.

Here are all the permutations of size 4 again, this time visualized as matchings.

Now, at this point I am very tempted to go off on a tangent exploring group theory, symmetry groups, and all sorts of other stuff, but I shall restrain myself (for now!).

Binomial coefficients

Another piece of the equation is the binomial coefficient \binom n i. But of course we already know what binomial coefficients count—\binom n i is the number of ways to choose i things out of n, that is, the number of size-i subsets of a size-n set. (I also talked about this last time.)

Exponentiation and functions

What about (k+i)^n? What does that count? It turns out that exponentiation corresponds to counting functions: in particular, b^a is the number of functions from a set of size a to a set of size b. Why is that? Well, for each of the a elements of the domain, we have b choices for where a function could send it, and each of these choices is independent—so the total number of choices is b \cdot b \cdot \dots \cdot b = b^a.

For example, here are all of the 3^3 = 27 functions from a size-3 set to a size-3 set:

Hmmm… this looks familiar! Note that some of these functions are matchings, and some aren’t. Perhaps you’re starting to get an inkling now why I introduced the idea of permutations as matchings…

All the pieces are almost in place now. The one piece of the equation we still haven’t yet talked about is that mysterious (-1)^{n-i}. It certainly doesn’t make sense to interpret that as the number of functions from a set of size n-i to a “set of size negative one”, because of course there is no such thing as a set with a negative size. So how can we interpret it combinatorially? The answer lies in something called the Principle of Inclusion-Exclusion (or PIE for short), which will be the subject of my next post!

Posted in combinatorics, pictures | Tagged , , , , | 2 Comments

Combinatorial proofs

Posted on February 17, 2012 by

Continuing from a previous post, we found that if we begin with nth powers of (n+1) consecutive integers and then repeatedly take successive differences, it seems like we always end up with the factorial of n, that is, n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n. We then derived an algebraic expression for the result of the iterative difference procedure. So the goal now is to prove that

\displaystyle \sum_{i=0}^n (-1)^{n-i} \binom n i (k+i)^n = n!

that is,

\displaystyle (-1)^n \binom n 0 k^n + (-1)^{n-1} \binom n 1 (k+1)^n + \dots + \binom n n (k+n)^n = n!

Now, it’s possible (probable, in fact) that this can be proved by purely algebraic means. If you come up with such a proof I would love to see it! But I must confess that I spent several hours banging my head against it (algebraically speaking) without making any progress. Eventually I turned to the idea of a combinatorial proof.

What do I mean by that? Combinatorics is the subfield of mathematics concerned with counting. The essence of a combinatorial proof is to show that two different expressions are just two different ways of counting the same set of objects—and must therefore be equal. I’ve described some combinatorial proofs before, in counting the number of ways to distribute cookies.

As another simple example, consider the binomial coefficient identity

\displaystyle \binom n k = \binom {n-1}{k} + \binom{n-1}{k-1}

It’s certainly possible to prove this algebraically, by expanding out the binomial coefficients (using \binom n k = \frac{n!}{k!(n-k)!}), but we can give a more elegant proof, based on the fact that \binom n k is the number of ways to choose a subset of k things out of a set of n things. For example, here are the \binom 5 3 = 10 ways to choose three things out a set of five:

Size-3 subsets of a set of size 5

Consider the first element of the size-n set. Every subset of size k either includes this first element, or it doesn’t. The number of size-k subsets which do not include the first element is \binom{n-1}{k}, since that’s the number of ways to choose k things from the remaining n-1 elements. The number of size-k subsets which do include the first element is \binom{n-1}{k-1}, because they correspond to choosing k-1 of the remaining n-1 things. Therefore \binom n k = \binom{n-1}{k} + \binom{n-1}{k-1}.

Here’s an illustration of how this works in the particular case when n = 5 and k = 3:

Size-3 subsets of 5 elements, grouped by first element

Notice how the ten subsets from above have been split into two groups: the first group, on the left, are those that don’t include the first element; you can see that each of them corresponds to one of the \binom 4 3 = 4 size-3 subsets of the remaining four elements. The second group, on the right, are those that do include the first element; each corresponds to one of the \binom 4 2 = 6 size-2 subsets of the remaining four elements.

So that’s the idea of a combinatorial proof. And we want to do something similar for the identity we are trying to prove—although, of course, it’s going to be a bit more difficult!

You might have fun trying to think about what a combinatorial proof of our target equation might look like; although if you don’t have much experience with combinatorics you may have trouble coming up with what sorts of things the two sides of the equation might be counting! That’s what I’ll talk about in my next post.

Posted in combinatorics, pictures, proof | Tagged , , | 12 Comments