A sequence of Fibonacci facts

The Hampshire College Summer Studies in Mathematics program has what it calls an “Interesting Test” that interested students are invited to take as part of their application. Their web page offers a sample of past test problems. One of these, under the heading “Problems which at first seem to lack sufficient information”, is as follows:

From the third term on, each term of the sequence of real numbers a_1, a_2, \ldots, a_{10} is the sum of the preceding two terms; that is, a_n = a_{n-1} + a_{n-2} for n = 3, 4, 5, \ldots, 10. If a_7 = 17, what is the sum of all the ten terms?

I’d heard this one before (though it’s hard to find a source for things like this – the cloesst I could find was this Math StackExchange question. The solution is as follows: we can write a_3, a_4, \ldots, a_{10} as linear combinations of a_1, a_2. In particular we have a_3 = a_1 + a_2, a_4 = a_1 + 2a_2, \ldots, a_{10} = 21a_1 + 34 a_2, where the general term is a_n = F_{n-2} a_1 + F_{n-1} a_n (we’ll use this later). Here F_n is the nth Fibonacci number, where F_1 = F_2 = 1, F_n = F_{n-1} + F_{n-2}. Adding everything up we get

a_1 + \ldots + a_{10} = \left( 1 + 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21\right) a_1 + \left( 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 \right) a_2

and doing those sums gives a_1 + \ldots + a_{10} = 55 a_1 + 88 a_2. But a_7 = 5 a_1 + 8 a_2, and so the sum is just 11a_7 = 11 \cdot 17 = 187. For example, consider the sequence with a_1 = 5, a_2 = -1:

5, -1, 4, 3, 7, 10, 17, 27, 44, 71

which you can easily verify sums to 187. In the case where you actually have the whole sequence, this is a reasonably well-known “arithmetic trick” that one can show grade school children! The HCSSiM version, of course, doesn’t let you see the whole sequence.

But are there similar tricks to this with shorter or longer sequences? That’s usually the way with the Fibonacci numbers; facts about them tend to be parametrizable. A bit of experimentation shows us that with six terms we have

a_1 + \ldots + a_6 = 8 a_1 + 12 a_2 = 4 (2a_1 + 3a_2) = 4 a_5.

See for example the series 4, 1, 5, 9, 14, 23; its sum, 56, is four times its fifth term. And with fourteen terms we have

a_1 + a_2 + \ldots + a_{14} = 377 a_1 + 609 a_2 = 29 (13a_1 + 21a_2) = 29 a_9

(I’ll leave you to come up with your own example.) It would appear that we have a_1 + \ldots + a_{4k+2} = L_{2k+1} a_{2k+3}, where the L_j are the Lucas numbers L_1 = 1, L_2 = 3, L_n = L_{n-1} + L_{n-2}. Consider the sum of the first 4k+2 terms satisfying a Fibonacci recurrence:

a_1 + a_2 + \ldots + a_{4k+2} = F_{4k+2} a_1 + (F_{4k+3}-1) a_2.

Now we have F_{4k+2} = F_{2k+1} L_{2k+1} and F_{4k+3}-1 = F_{2k+2} L_{2k+1}. These are both special cases of the identity givnen in Wikipedia, F_{n+k} + (-1)^k F_{n-k}= L_k F_n. So we have

a_1 + a_2 + \ldots + a_{4k+2} = F_{2k+1} L_{2k+1} a_1 + F_{2k+2} L_{2k+1} a_2 = L_{2k+1} (F_{2k+1} a_1 + F_{2k+2} a_2) = L_{2k+1} a_{2k+3}.

So the sum of a fourteen-term Fibonacci sequence is equal to a multiple of the ninth term; the sum of a ten-term Fibonacci sequence, a multiple of the seventh term; the sum of a six-term Fibonacci sequence, a multiple of the fifth term. What of a sum of a two-term Fibonacci sequence? We get a_1 + a_2 = L_1 a_3. Recall L_1 = 1 — the sum of the first two terms is, trivially, a multiple of the third term.

(I don’t claim this is original. Only that I had some fun thinking about it. That probably means I need to get a life.)

Another Trump dump

Terry Tao’s open thread for mathematicians on the immigration executive order, not exactly a follow-up to it ought to be common knowledge that Donald Trump is not fit for the presidency of the United States of America. Tao writes:

mathematical research is a transnational activity, in that the specific nationality of individual members of a research team or research community are (or should be) of no appreciable significance for the purpose of advancing mathematics.

Not surprisingly, then, given the current political situation, 90 percent of people identifying themselves as “mathematician” donating money to US political campaigns give to Democrats, according to analysis by Verdant Labs. Only 85 percent of those calling themselves “Professor of Mathematics” do.  One possible explanation is the those identifying as “professor of mathematics” identify more with their position as educators, and education doesn’t have the same “transnational” quality.

You can download the data from the FEC if you want! I suspect there’s something interesting in here… let’s see how my new laptop handles those twenty million records.

And please point me to interesting analysis of FEC data on campaign contributions that’s already been done! A couple things I’ve seen from the data science community:

  • Someone named Gary did some analysis in November of 2015, for the 2016 presidential cycle as it had unfolded thus far in Ohio
  • Verdant Labs has also looked at the politics of first names .

But there is surprisingly little out there, given that this is such an interesting data set!

If you want to do something more useful than navel-gazing at data, I recently came across Data for Democracy, and Moon Duchin is organizing a summer school on the geometry of redistricting, including some training in being an expert witness in gerrymandering cases. Will someone write the gerrymandr R package?

11:57:30

The Doomsday clock, of the Bulletin of the Atomic Scientists, is back in the news. It’s 11:57:30. It was 11:57; the thirty-second increment is unpresidented [sic]. The amount of time until midnight is supposed to indicate how close we are to, well, Doomsday.

I feel reasonably sure that I’ve seen somewhere a suggestion that the Doomsday clock could be calibrated such that the probability of Doomsday is proportional to the reciprocal of the time towards midnight. If I had to guess this is an idea of Douglas Hofstadter but I don’t have his books at hand right now. (This is annoyingly hard to Google, because the Doomsday argument gets in the way.)

Some people have objected to the thirty-second news as unnecessary fine-tuning. But in this reciprocal view that isn’t so strange; it corresponds to adjusting the probability of Doomsday from, say, one per thirty years to one per twenty-five years. There have been moves from five to six minutes before, to which this is proportional.  Also, the clock was at 11:57; it’s only been at 11:58 once before, after the US and Soviet Union did thermonuclear tests in close temporal proximity in 1953.  So unless they want to say it is literally the worst it has ever been, two and a half minutes to midnight it is.

Here’s the full statement of the Bulletin. They appear to be saving themselves some room:

The board’s decision to move the clock less than a full minute—something it has never before done— reflects a simple reality: As this statement is issued, Donald Trump has been the US president only a matter of days.

Let’s see what happens next year.

Luck

Simon Parkin for Nautilus on how luck is engineered into video games.  Some examples include near misses on slot machines (it’s actually illegal to deliberately manipulate these into happening, although since slot machines are now fully electronic it’s technically possible), the gameReally Bad Chess (chess with random peaces), and combat mechanics in video games that are tweaked to not follow the laws of probability. Because people get mad at actual randomness.

A calendar puzzle with some wrinkles

FiveThirtyEight’s puzzle feature, the Riddler, had a puzzle this week called Don’t throw out that calendar!.  (Spoilers below; also, I’m delaying posting this until after the submission period for solutions ends.). This puzzle is due to Ben Zimmer.

Sometime in the 21st century, the following conversation takes place:

“Don’t throw out that calendar! You could reuse it in the future, when the days and dates on the calendar match up again.”

“OK, but that won’t happen for a long time. Forty years, in fact.”

“You’re right! In fact, this calendar has never had a 40-year gap before.”

What year is it?

We can start by observing that there are 14 possible calendars.  To know what calendar we can use in a given year, we have to know whether it’s a common (non-leap) or leap year, and the day of the week of one particular day.    Let’s pay attention to what John Conway called “Doomsday”, i. e. the last day of February (February 28 in common years, and February 29 in leap years).  Doomsday moves forward one day in the week each year, except two days in each leap year – so, for example, Doomsday (February 28) 2015 was a Saturday, Doomsday (February 29) 2016 was a Monday, and Doomsday (February 28) 2017 will be a Tuesday.

So let’s consider when a 40-year gap will happen.  A 40-year gap can’t begin with a common year.   Say the year Y is the year after a leap year; then Doomsday of Y+6 will be the same as Doomsday of Y, since over those six years Doomsday will move forward six days in the week, plus one day for the leap year.  If Y is two or three years after a leap year, then Y + 11 and Y will have the same Doomsday – Doomsday moves forward 11 days, plus three for the leap years.  (This is basically cribbed from the calendar FAQ.

The exception is if Y is very near the end of a century that isn’t divisible by 400 – near enough that one of the otherwise intervening leap years would be a common year.  In any of these cases Y and Y + 12 share a calendar – there are two intervening leap years.

(In most cases Y and Y + 28 share a calendar – that is, if no end-of-century common year intervenes. But we’d still have to do the casework anyway.)

So we must be in a leap year.  But a 40-year gap, from Y to Y + 40, should lead to a Doomsday being one day later (40 + 10 = 50, which is one more than a multiple of seven)  We must be in a leap year for which there are only NINE leap years in the next 40 – i. e. we’re in one of 2064, 2068, …, 2096 – since 2100 isn’t a leap year.   But the calendars 2064 and 2068 will be repeated in 2092 and 2096 (28 years later, with 7 leap years), and 2092 and 2096 will be repeated twelve years later (with two leap years).  So we must be in one of the five years 2072, 2076, 2080, 2084, and 2088.

Which one is it?  See the note “You’re right! In fact, this calendar has never had a 40-year gap before.”  By the same reasoning as above, 40-year gaps in the past could have only happened in starting in one of the leap years 1672-1688, 1772-1788, 1872-1888, since the Gregorian calendar – which insituted our current leap-year policy and thus the nine-in-forty loophole started in 1582.  (1600 and 2000 were leap years, so 15xx and 19xx candidates are out.)

Doomsday in 1672 in the Gregorian calendar was Monday. I cheated by looking it up. For example you can type ncal -sFR 1672 at your friendly Unix prompt, where “FR” is the country code for France, a country that adopted the Gregorian calendar at the beginning. Honestly, it doesn’t matter what day of the week Doomsday in 1672 is, only the relationships between the Doomsdays. In 1772 Doomsday is Saturday (124 days later in the week, that is, 100 years plus 24 leap years); in 1872 it’s Thursday.  So we can work out the doomsdays for each leap year. These are:

1672 through 1688: Mon, Sat, Thu, Tue, Sun

1772 through 1788: Sat, Thu, Tue, Sun, Fri

1872 through 1888: Thu, Tue, Sun, Fri, Wed

2072 through 2088: Mon, Sat, Thu, Tue, Sun

All seven days of the week occur here, so the puzzle seems to be broken.  But if we’re in a country which switched calendars after 1672 but before 1772 – like, say, Great Britain and its colonies, which changed over in 1752 – then the doomsday-Monday calendar won’t have occurred yet but the other six have. (Again from the calendar FAQ), we could also be pretty much anywhere else in Protestant-dominated Europe or colonies thereof.) The answer is 2072.