Fibonacci Forgeries


Scientific American, May 1995

A toast, ladies and gentlemen: To the Queen!” We stood, dutifully raised our glasses and murmured the sovereign’s name. It should have been a poignant moment, but it was spoiled by the person next to me, who flopped back into his chair and muttered, “Thank God, now I can smoke!” (It is a quaint British custom that at a formal dinner no one may smoke before the party drinks to the queen’s health.)

“I’d rather you didn’t,” I said. “I’m a nonsmoker.”

“You had the smoked salmon,” he said and roared with laughter as he lit a cigarette. I wrinkled my nose and glanced at his badge: Richard Byrd. He had penciled in, “Call me Dicky.”

“The salmon, by the way, was terrible,” I told him. “In fact, I think it was really dogfish dyed orange.” He did not look surprised. The annual dinner of CAT-DOG (the Charitable Association for Tax-Deductible Offerings of Generosity) was always a disaster.

“I wondered why the fish was wearing a flea collar,” said the lady on my left. I had met her at other gatherings: Amanda Bander-Gander, a leading light of the local Animal Protection Society.  

“No, dear, you just dropped your napkin ring on it,” her husband yelled from five places down on the opposite side of the table. Alexander Bander-Gander, a lawyer, was sandwiched between Athanasius Fell, a doctor, and Dennis Racket, an old friend of mine from the tennis club.

“So what business are you in?” Dicky asked me.

I leaned closer to him and whispered, “I’m a mathematician.”

As usual, though I had spoken below the threshold of aural perception, it was a party-stopper. The entire table went silent.
“I was never—” he began.

“Any good at math at school,” I finished. “That’s what they all say.”

“Hated it then,” Athanasius mumbled. “Still do.”

“I must be the exception!” a voice boomed at my right. “Absolutely loved it! Name’s Adam Smasher. I’m a nuclear physicist. I have a little puzzle I’ll ask all of you. What’s the next number in the sequence 1, 1, 2, 3, 5, 8, 13, 21?”

“Nineteen,” I grunted automatically, while battling with a bread roll seemingly baked with cement.

“You’re not supposed to answer,” he said. “Anyway, you’re wrong—it’s 34. What made you think it was 19?”

I drained my glass. “According to Carl E. Linderholm’s great classic Mathematics Made Difficult, the next term is always 19, whatever the sequence: 1, 2, 3, 4, 5—19 and 1, 2, 4, 8, 16, 32—19. Even 2, 3, 5, 7, 11, 13, 17—19.”

“That’s ridiculous.”

“No, it’s simple and general and universally applicable and thus superior to any other solution. The Laplace interpolation formula can fit a polynomial to any sequence whatsoever, so you can choose whichever number you want to come next, having a perfectly valid reason. For simplicity, you always choose the same number.”

“Why 19?” Dennis asked.

“It’s supposed to be one more than your favorite number,” I said, “to fool anyone present who likes to psychoanalyze people based on their favorite number.”

“Nonsense. I’ll tell you the real answer,” Adam said. “Each number is the sum of the previous two. So the next is 13+21, or 34, then 55, then 89, then 144 and so on. It’s the—”

“Fibonacci sequence,” I interrupted. “God, I’m so fed up with the blasted Fibonacci sequence! Even the name’s phony! ‘Leonardo Fibonacci, son of Bonacci!’ That’s a nickname invented by Guillaume Libri in 1838, long after Fibonacci died. The famed Fibonacci was in fact named Leonardo Pisano Bigollo. Pisano means that he lived in Pisa; no one knows what Bigollo means. At any rate, his sequence ought to be called the Leonardo Pisano Bigollo sequence, except that’s too long.”

Fibonacci or Forgery?

Sequence 1 is 2, 3, 5, 8, 13 ... an, where an equals 1 plus the sum of the first n terms of the Fibonacci sequence. For example, a1 = 1 + 1 = 2; a2 = 1 + (1 + 1) = 3; a3 = 1 + (1 + 1 + 2) = 5 and so on.

Sequence 2 is 1, 3, 8, 21, 55 ... an, where an equals the sum of the first n terms of the sequence formed by removing every other Fibonacci number. So a1=1; a2=1+2=3; a3 = 1 + 2 + 5 = 8 and so on.

Sequence 3 is 1, 1, 2, 3, 5, 8 ... an, where an is the number of ways in which you can arrange n coins in horizontal rows such that all the coins in each row touch and every coin above the bottom row touches two coins in the row below it.

Sequence 4 is 1, 2, 5, 13 ... an. It is the same as sequence 3, except that now n is the number of coins in the bottom row.

Sequence 5 is 1, 2, 5, 13 ... an, where an=(n – 1)2n–2 + 1.

Sequence 6 is 1, 2, 5, 13 ... an, as defined by the number of disconnected graphs with n + 1 vertices.

Sequence 7 is 1, 1, 2, 3, 5, 8 ... an, where anequals the integer nearest to ((1 +  5)/2)n/  5.

Sequence 8 is 1, 2, 5, 13, defined by the number of connected graphs with n + 2 vertices having just one cycle.

Sequence 9 is 1, 2, 5, 13 ... an, where an is the coefficient of xn+2/(n + 2)! in the power series solution to the differential equation y¢¢ = exy, which starts y = 1 + x 2/2!+ x 3/3! + 2 x 4/4! + 5 x 5/5! + 13 x 6/6!...

Sequence 10 is 1, 2, 5,, where an equals an–1+nan–2 , when a-1=a0=1/2.

Sequence 11 is 2, 3, 5, 8, In this sequence, apartment blocks of n floors are to be painted blue and yellow, with the rule that no two adjacent floors can be blue. (They can, however, be yellow.) Let an be the number of ways to paint a block with n floors.

“You mathematicians have a lot of attitude,” Dicky remarked. “At least, an attitude that differs from most other people’s.”

“Proof,” Adam declared. “Mathematicians always want to prove things. That’s certainly a strange attitude. Never understood why myself. If you keep trying it, and it keeps working, it’s got to be right! So why waste time getting into all sorts of logical tangles proving the silly thing?”

“Well, why do you physicists bother doing experiments? If a theory tells you what you want to hear, why not just assume it’s true?”

“Because you can’t just go around believing theories without testing them!”

“And mathematicians don’t think you can go around believing theorems without proving them. Alexander, why do lawyers insist on cases being tried in court? Why not just let the judge look at the evidence and decide whether the defendant has committed the crime?”

“You can’t do that! There could be a miscarriage of justice!”

“Right. That’s what mathematicians worry about when they insist on proofs. They don’t want to find out later they were wrong. It might be embarrassing.”

Adam shook his head sadly. “You know full well it’s not like that. Mathematics is basically simple. If you can see an obvious pattern, it can’t be coincidence. Why bother to prove it?”

I thought for a few seconds. “I’ll give you an example. Here’s a sequence, and I want you to tell me the next number.”
“I’ll do my best.”
“1, 1, 2, 3, 5, 8, 13, 21, 34, 55,” I said.
He looked puzzled. “Don’t be silly. I just asked you that one. It’s the Fibonacci sequence.”
“Is it? Then what’s next?”
“89,” Adam replied.
“Wrong. It’s 91.”
“But it looks just like the—”

“You’re leaping to conclusions, Adam, based on previous prejudices. Most injudicious. Your sequence was the Fibonacci sequence, but the nth term in my sequence is the least integer not less than Öe n–2, where Öe = 2.71828, the base of natural logarithms. I want the 11th term, which is the least integer not less than Öe9, or 90.017. That’s 91.”

“Humph. Well, that’s an accident, a rare exception. I’ll believe you if you can show me some more examples of misleading sequences,” Alexander interjected. “Can you? Or have you exhausted your repertoire?”

“There are hundreds,” I said. “It’s easier than you think. Richard K. Guy, a mathematician at the University of Calgary, collects them. He refers to them all as the Strong Law of Small Numbers. There aren’t enough small numbers to meet the many demands placed on them, so what look like patterns involving small numbers might just be coincidence. And often are.”

I showed them 11 sequences that looked like the Fibonacci numbers, or the alternate Fibonacci numbers 1, 2, 5, 13 and so on (see box above). I asked them to decide which were really Fibonacci sequences and which were Fibonacci forgeries (see box below for answers).

My companions began to argue about whose solution was right when I proposed one last puzzle. “What is the next term in the sequence 3, 5, 7, 11, 13, 17, 19...”—I carried on for some time listing the odd primes—“...331, 337?”

“Those are the odd primes,” Adam said. “You can’t generate that many primes by accident. The next term must be—uh—347.”

“Are you sure?” I asked quietly.

Solutions to the Misleading Sequences

Sequence 1: Fibonacci. For example, to form a6, you add 8, the sixth term in the Fibonacci sequence. The sum is 8+13, a sum of consecutive Fibonacci numbers. By definition, then, the answer, 21, is itself a Fibonacci number. This pattern continues.

Sequence 2: Fibonacci. For example, to go from a5 to a6, you add 89. The sum is 55+89, a sum of consecutive Fibonacci numbers. By definition, then, the answer, 144, is itself a Fibonacci number. This pattern continues.

Sequence 3: Forgery. The sequence continues 12, 18, 26.

Sequence 4: Fibonacci. The proof depends on the identity f2n–1 = f2n–3 + 2f2n–5 + 3f2n–7 + ... + (n–1) f1 + 1 for Fibonacci numbers fn.

Sequence 5: Forgery. The sequence continues 33, 81, 193.

Sequence 6: Forgery. The sequence continues 44, 191, 1,229, 13,588.

Sequence 7: Fibonacci. This pattern follows from Binet’s formula f_n = [((1 + \sqrt{5})/2)^n + ((1 - \sqrt{5})/2)^n]/ \sqrt{5}.

Sequence 8: Forgery. The sequence continues 33, 89, 240, 657, 1,806.

Sequence 9: Forgery. The sequence continues 36, 109, 359, 1,266.

Sequence 10: Forgery. The sequence continues 38, 116, 382.

Sequence 11: Fibonacci. Consider, for example, a five-floor building. The fifth floor can be either yellow or blue. If it is yellow, the rest of the building can be painted in any possible way for a four-floor building. If it is blue, the fourth floor must be yellow, and the rest of the building can be painted in any possible way for a three-floor building. So a5=a4+a3, as it is for Fibonacci numbers. The pattern is general.

Odd Prime Sequence: Forgery. The sequence 3, 5, 7, 11...331, 337 and so on consists of all the numbers n that divide 2n–1–1 exactly. The next term is 341, which is not prime (11 x 31=341) but divides 2340–1.



MATHEMATICAL GAMES: PATTERNS IN PRIMES ARE A CLUE TO THE STRONG LAW OF SMALL NUMBERS. Martin Gardner in Scientific American, Vol. 243, No. 6, pages 18–28; December 1980.
A DIARY ON INFORMATION THEORY. Alfréd Rényi. Wiley, 1987.
THE STRONG LAW OF SMALL NUMBERS. Richard K. Guy in American Mathematical Monthly, Vol. 95, No. 8, pages 697– 712; October 1988.
THE SECOND STRONG LAW OF SMALL NUMBERS. Richard K. Guy in Mathematics Magazine, Vol. 63, No. 1, pages 3–20; February 1990.