Huh?

Via X=Why?, I found an article on how a criminal investigation lab in California is inviting students to come in and showing them that math is useful for solving crimes. (In the CSI way -- figuring out how blood splatters, say -- not in the Numb3rs way.) This is certainly a good thing to do.

But can you make sense of this?

Craig Ogino, the department's crime lab director, started the event by offering a prize of $10 to the student who could use trigonometry to determine the number in gallons of a mixture used to make methamphetamine, based on his sketch.

I'm assuming that trigonometry was actually used for something else -- like, say, the aforementioned blood splattering analysis, seen later in the article -- and that the reporter made a mistake. But I'm not totally sure. Any thoughts?

Kids these days...

Shitload of math due Monday, from The Onion:

Making matters worse, students said, was their math textbook, which reportedly doesn't even have any of the freaking answers in the back.

How would these kids feel if they learned that eventually the questions aren't even in the book, but you have to come up with them yourself?

2008 Putnam problems

This year's Putnam exam problems, via 360.

I haven't thought about these, but I might as a break from writing things up over the next few days.

How could you guess the formula for the sum of the first n fifth powers?

The following three formulae are reasonably well known:

1 + 2 + 3 + ... + n = n(n+1)/2

1² + 2² + 3² + ... + n ² = n(n+1)(2n+1)/6

1³ + 2³ + 3³ + ... + n ³ = (n(n+1)/2)²

(The sums of first and second powers arise pretty often naturally; the sum of cubes is rare, but it's easy to remember because the sum of the first n cubes is the square of the sum of the first n natural numbers.)

The first member of this series I can't remember is the following:

1⁴ + 2⁴ + 3⁴ + ... + n ⁴ = n(n+1)(2n+1)(3n²+3n-1)/30

and generally, the sum of the first n kth powers is a polynomial of degree k+1.

I ran into these formulas, which I'd seen plenty of times before while perusing the book Gamma: Exploring Euler's Constant by Julian Havil, which I had heard of a few years ago, forgotten about, and then found while browsing the library shelves. (Also in German, under the title GAMMA: Eulers Konstante, Primzahlstrände und die Riemannsche Vermutung.) This is a most interesting book, at least if you're someone like me who pretends to know number theory but really doesn't.

Anyway, back to the main story. Say I wanted to know the sum of the first n fifth powers. Well, there's a general method for finding the formula of the first k powers; it involves the Bernoulli numbers. But let's say I didn't know that. Let's say somebody hands me the sequence

1, 33, 276, 1300, 4425, 12201, 29008, 61776, 120825, 220825

in which the nth term, s_n, is the sum 1⁵ + 2⁵ + ... + n⁵ -- but doesn't tell me that's where the sequence comes from -- and challenges me to guess a formula for it in "closed form". (Smart-asses who will say that there are infinitely many formulas are hereby asked to leave.) How would I guess it?

Well, it can't hurt to find factorizations for these numbers. And if you do that you get

1, 3¹ 11¹, 2² 3¹ 23¹, 2² 5² 13¹, 3¹ 5² 59¹, 3¹ 7² 83¹, 2⁴ 7² 37¹, 2⁴ 3³ 11¹ 13¹, 3³ 5² 179¹, 5² 11² 73¹

and this seems interesting; these numbers seem to have lots of small factors. Furthermore, a fair number of them seem to have one largeish prime factor, which I've bolded. (Yes, I realize, 11 times 13 isn't prime, but I actually did think of it as a large factor.) What are the large factors that I observe in these numbers? They are

?, 11, 23, ?, 59, 83, ?, 143, 179, ?

and the nth of these is easily seen to be 2n² + 2n - 1. (Some terms don't show up from inspection of the factorizations because they get "lost in the noise", as it were.)

From there the rest is pretty easy. We see that often (but not always), s_n is divisible by 2n² + 2n - 1. You can check that for n = 1, 2, ..., 10, the term s_n is always divisible by (2n² + 2n - 1)/3. So now consider the sequence t_n = s_n / ((2n² + 2n - 1)/3). The numbers t₁ through t₁₀ are

1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025

and I recognized that all of these are squares; in particular t_n = (n(n+1)/2)².

Putting everything together, I get the conjecture that the sum of the first n fifth powers

s_n = n²(n+1)²(2n²+2n-1)/12

which could be proven by induction, but actually writing out the proof is best left to undergrads.

The method here is reminiscent of Enumeration of Matchings: Problems and Progress by James Propp. In that article, Propp lists various unsolved problems in the enumeration of tilings, and conjectures that some of them might have answers which are given by simple product formulas, because actually counting the tilings in question gave numbers with nice prime factorizations.

Edit, 9:13 pm: of course this is not the only method, or even the best method; it's just the method I played around with this morning. See the comments for other methods.

How to break into a keyless-entry car

Weak security in our daily lives (in English): basically, you can use a de Bruijn sequence to break into a car with keyless entry in what might be a non-ridiculous amount of time. I'm referring to the sort which have five buttons marked 1/2, 3/4, 5/6, 7/8, and 9/0, and a five-digit PIN that has to be entered. This trick takes advantage of the fact that the circuitry only remembers the last five buttons pressed, so if you press, say, 157393, then the car will open if the correct code is either 15739 or 57393. It is in fact possible to arrange things so that each key you press, starting with the fifth, completes a five-digit sequence that hasn't been seen before.

Of course, you shouldn't do this.

Via microsiervos (in Spanish).

Logic as machine language

Gil Kalai mentions a metaphor I hadn't heard of before about the foundations of mathematics:

To borrow notions from computers, mathematical logic can be regarded as the “machine language” for mathematicians who usually use much higher languages and who do not worry about “compilation.”

Of course there would be analogues to the fact that certain computer languages are higher-level than others as well. To take an example dear to me, the theory of generating functions might be at a higher level than the various ad hoc combinatorial arguments it's often introduced to students as a replacement of. I don't want to press this metaphor too hard because it'll break -- I don't think there are analogues to particular computer languages. But feel free to disagree!

You can't say you're a liar

From Family Guy:
"Chris, everything I say is a lie. Except that. And that. And that. And that. And that. And that. And that. And that."