MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Nontrivial question about fibonacci numbers?

I'm looking for a nontrivial, but not super difficult question concerning Fibonacci numbers. It should be at a level suitable for an undergraduate course.

Here is a (not so good) example of the sort of thing I am looking for.

a) Prove that every positive integer can be represented in binary over the basis of Fibonacci numbers. That is, show that for all $n$, there exist bits $x_1,\ldots,x_k$ such that $n = \sum_{i=1}^kx_iF_i$.

b) Give an algorithm to increment such numbers in constant amortized time.

Any ideas for better ones?

-
For a whole raft of such questions, see 1.2.8 of Knuth's The Art of Computer Programming, vol. 1. – Steve Huntsman Jan 15 2010 at 17:58
There are two kinds of such questions: one in which Fibonacci numbers appear in the statement, and another in which they do not and for which realizing that they are involved is a key to the answer. (Example of the second kind: how many sequences of coin flips of length $n$ have no instances of tails appearing twice?) Which type do you have in mind, or are you indifferent? – Pete L. Clark Jan 15 2010 at 18:11
I like your example. What's not so good about it? – Dan Piponi Jan 15 2010 at 18:26
TWICE IN A ROW, I meant of course. (I look forward to the day when comments are editable.) – Pete L. Clark Jan 16 2010 at 1:01
Ever heard of Zeckendorf's theorem? – J. H. S. Jan 16 2010 at 8:02

An accessible (and interesting) thing to look at with Fibonacci numbers is their periodicity modulo various integers, especially primes and prime powers. One example of an accessible result is that if $k(p)$ is the period of the Fibonacci numbers modulo a prime $p$, then $k(p)\mid p^2-1$. You can get sharper results by examining whether or not 5 is a quadratic residue mod $p$ (think of the importance of $\frac{1\pm\sqrt{5}}{2}$ to the Fibonacci numbers). You can prove things about this periodicity directly, or reduce the 2x2 matrix which Gowers mentions modulo $p$ and get the same thing, depending on what you'd like to emphasize to your students. Some good resources for this subject are

http://en.wikipedia.org/wiki/Pisano_period

http://euclid.math.temple.edu/~renault/fibonacci/fib.html

Another neat thing about the Fibonacci numbers is their appearance as sums of "diagonals" in Pascal's Triangle, as in this picture:

However, this fact is provable simply by induction, so maybe this is too easy for what you have in mind.

-
That sounds like a lot of fun. I might assign this as homework the next time I teach undergraduate number theory. – Pete L. Clark Jan 15 2010 at 18:22
Induction? Bah! It's a direct corollary of the combinatorial definition of the Fibonacci numbers in terms of tilings using 1x1 and 1x2 tiles. – Qiaochu Yuan Jan 15 2010 at 18:38
Something not-so-undergraduate about this topic which I was obsessed with for a while: If $k(p)\neq k(p^2)$, then the first case ($p\nmid xyz$) of Fermat's Last Theorem holds for the exponent $p$. Now, since Wiles proved the whole thing this is probably not as interesting anymore - I don't think it was even on most people's radar to begin with - but I think there's a lot more to be said for this approach. I consider it a (very, very long-term) goal of mine to get an alternate proof of FLT this way. – Zev Chonoles Jan 15 2010 at 18:42
It is true that $$F_{n}=\sum_{0\le{k}\le{n-1}}{n-1-k\choose k}$$ is rather trivial. Not so trivial is the following generalization due to L. Carlitz $$\sum_{0\le k_{0}\le{n-1}, 0\le k_{1}\le{n-1},…, 0\le k_{r-1}\le{n-1}}{n-k_{0}\choose k_{1}}{n-k_{1}\choose k_{2}}{…}{n-k_{r-1}\choose k_{0}}=F_{rn}/F_r.$$ – Johann Cigler Nov 19 2010 at 17:09
Tilings using 1x1 and 1x2 tiles? Bah! It's a direct observation that the "right parents" of each diagonal comprise the previous diagonal, while the "left parents" comprise the twice-previous diagonal. – Sridhar Ramesh Feb 19 2012 at 0:13

Here you have some of the coolest ones I have heard of:

1) Let $a$ be a positive integer. Then $a$ is a Fibonacci number if and only if at least one member of the set {$5a^{2}-4, 5a^{2}+4$} is a perfect square.

I think the result is original with Prof. Ira Gessel.

2) Let $\phi$ denote the Euler totient function. Prove that $\phi(F_{n}) \equiv 0 \pmod{4}$ if $n \geq 5$.

The proof consists of an unexpected application of Lagrange's theorem in Group Theory. Guess there are some other ways to prove it, but that approach will always remain my cup of tea. The problem was posed and solved in the Monthly in the 70's (if my memory serves me right). Look for all entries by Clark Kimberling in that magazine and you'll surely find it.

3) Can you find $(a,b,c) \in \mathbb{N}^{3}$ such that $2 < a < b < c$ and $F_{a} \cdot F_{b} = F_{c}$?

This problem would be trivial if instead of the $\cdot$ we had placed a plus sign there. In any case, there is no need to panic with this proposal. All you need to recall is the corresponding primitive divisor theorem.

4) Ben Linowitz mentioned above a beautiful result by Professor Florian Luca, namely:

There aren't any perfect numbers in the Fibonacci sequence.

I read the paper in my junior year and I didn't find it that hard to follow. The easy part of this cute note resides in the proof of the fact that there are no even perfect numbers in the Fibonacci sequence. Guess this result is interesting enough to deserve consideration in those lectures that you intend to give. If this proposal is not exactly your idea of excitement, you can take a look at some of the other papers by Professor Florian. He writes a lot about recurrence sequences. Another theorem of his, closely related with the subject matter of this discussion, ascertains that

There is no non-abelian finite simple group whose order is a Fibonacci number.

5) Last but not least... Prove that the sequence {$F_{n+1}/F_{n}$}$_{n \in \mathbb{N}}$ converges and use this fact to derive the continued fraction development for the golden ratio.

This one should be well-known, yet it would be nice to see what your students come up with...

Added (Nov 20/2010) I've just noticed that the Fibonacci Assn. has made available the articles published in The Fibonacci Quarterly between 1963 and 2003. I'm sure you will find plenty of additional material among those files that they have so generously released for our enjoyment. For instance, the seminal paper by J. H. E. Cohn that K. Buzzard mentions below can be found here.

-
An alternate proof of (3) probably follows from the asymptotic formula for $F<sub>n</sub>$; $F_m F_n$ is between $F_{m+n-2}$ and $F_{m+n-1}$. I have not worked out the details. – Michael Lugo Jan 17 2010 at 1:06
These are very striking results. Already I find 1) very surprising! – Pete L. Clark Apr 9 2010 at 4:04
Seriously I only find (1) and (5) of any interest. The rest are basically negative results (including (2) which is equivalent to saying that no Fibonacci number beyound $3$ is a power of a prime $\equiv 3\pmod 4$) and not particularly exciting (though this does not mean their proofs are simple!). As for (1), this looks to me like a variation on the Pell theme: if $a$ is even, then we are talking about whether $\left(\frac{a}{2}\right)^2\pm 1$ is a perfect square, which is Pell. I assume that the general case is, similarly, a matter of "Vieta jumping" (inductively making the unknowns ... – darij grinberg Nov 22 2010 at 21:42
... smaller by means of jumping from one rational solution to another via Vieta). – darij grinberg Nov 22 2010 at 21:42
Sorry, I menat $\frac15\left(\left(\frac{a}{2}\right)^2\pm 1\right)$. – darij grinberg Nov 22 2010 at 21:44

In 1964 J. H. E. Cohn proved that the largest square in the Fibonacci sequence was 144. The proof uses standard facts about squares mod $p$, up to and including quadratic reciprocity, in an ingenious way. It's MR0163867 at Math Reviews if you want to chase this up. This is one of those proofs that you can easily read and understand, but it would be a devil to discover yourself. I have given this problem to undergraduates as a super-long exercise with hints.

-
Perhaps I should say that Samir Siksek and his co-authors have used decidedly non-undergraduate level mathematics to find all the perfect powers in the Fibonacci sequence (8 is the largest cube and there are no higher powers other than 1). Their work was published in the Annals recently. – Kevin Buzzard Jan 18 2010 at 10:53
I'd always thought that was a famous and obviously impossible open problem ... – gowers Nov 19 2010 at 16:31
You were dead right too, until a couple of years ago. The proof uses Wiles' machinery and transcendence methods. – Kevin Buzzard Nov 19 2010 at 19:27

The relation used by Matiyasevich (Matijasevich, Матиясевич), the one to which N. Takenov alluded above/below, is the following:

If $F_{n}^{2}|F_{m}$ then $F_{n}|m$ ...... (20)

In the 1992 Fall issue of the Intelligencer there was a note by Matiyasevich where he explained, among other things, the importance of that relation on his work concerning Hilbert's tenth problem. Here you have an excerpt from that note:

"It is not difficult to prove this remarkable property of Fibonacci numbers after it has been stated, but it seems that this beautiful fact was not discovered until 1969. My original proof of (20) was based on a theorem proved by the Soviet mathematician N. Vorob'ev in 1942 but published only in the third argumented (sic) edition of his popular book [on the Fibonacci sequence]... I studied the new edition of Vorob'ev book in the summer of 1969 and that theorem attracted my attention at once. I did not deduce (20) at that time, but after I read Julia Robinson's paper I immediately saw that Vorob'ev's theorem could be very useful. Julia Robinson did not see the third edition of Vorob'ev's book until she received a copy from me in 1970. Who can tell what would have happened if Vorob'ev had included his theorem in the first edition of his book? Perhaps, Hilbert's tenth problem would have been "unsolved" a decade earlier!"

-

Closely related to Zev's answer is that if $p$ is a prime not equal to $2$ or $5$, then $F_p \equiv \left( \frac{p}{5} \right) \bmod p$. The Fibonacci numbers also have a special relationship to continued fractions related to the second part of Nurdin's answer which I wrote an old blog post about here. There's a lot to say about them, so I wish you'd be a little more specific!

Edit: For example, one of my favorite Fibonacci exercises (which is somewhere in Stanley) is to write down the generating function for $\sum_{n \ge 0} F_{n+1}^2 x^n$ with no computation, using the fact that $F_{n+1}$ is the number of ways to tile a board of length $n$ with tiles of length $1$ and $2$, interpreting $F_{n+1}^2$ as the number of pairs of such tilings, and determining the "prime" tilings that can occur (the fancy keyword here is "monoid factorization").

Edit #2: While I'm on a combinatorics bent, there is another relationship between the Fibonacci numbers and continued fractions, but this time of power series. The generating function for the Catalan numbers can be described as a continued fraction corresponding to a recursive definition of ordered rooted trees, and one of the "convergents" of this power series is the generating function for the even Fibonacci numbers, which "explains" why the even Fibonacci numbers approximate the Catalan numbers. I also wrote a blog post about this here. There's a lot of interesting stuff here, although I'm not sure how to convert it into a good problem.

-
Another neat connection between Fibonacci numbers and tilings: the Fibonomial coefficients! en.wikipedia.org/wiki/Fibonomial_coefficient math.hmc.edu/~benjamin/papers/Fibonomial.pdf – Zev Chonoles Jan 15 2010 at 19:26
Yet another relation between tilings and Fibonacci numbers - this one was posed in IBM's ponder this challenge (domino.research.ibm.com/Comm/wwwr_ponder.nsf/…). The site provides a rough solution in the asymptotic regime but the exact expression would involve Fibonacci numbers. – Dinesh Apr 8 2010 at 18:41
The $F_p\cong\left(\frac{p}{5}\right)\mod p$ congruence is actually a rewriting of the quadratic reciprocity law for the pair $\left(p,5\right)$. In fact, working modulo $p$, we can have two cases: either $5$ is a square mod $p$, so there is some $\sqrt 5\in \mathbb F_p$, thus also a golden section $\phi\in\mathbb F_p$, which satisfies $\phi^{p-1}=1$ (all in $\mathbb F_p$); or $5$ is not a square mod$p$, in which case we must extend $\mathbb F_p$ to obtain a $\sqrt 5$ element and thus a golden section $\phi$, and this $\phi$ does not satisfy $\phi^{p-1}=1$ anymore ... – darij grinberg Nov 22 2010 at 21:53
... but instead $\phi^{p^2-1}=1$. Now, using Binet, it is easy to see that $F_p\equiv \left(\frac{p}{5}\right)\mod p$ if and only if $\phi^{2p}=1$ in $\mathbb F_p$ or the extension of $\mathbb F_p$ we are working in. The rest is clear. – darij grinberg Nov 22 2010 at 21:54
@darij: indeed. Perhaps you might be interested in helping me solve this math.SE problem: math.stackexchange.com/questions/2483/… – Qiaochu Yuan Nov 22 2010 at 22:27

Two formulas relating $\pi$ and the Fibonacci sequence.

$$\pi=\lim\limits_{n\to\infty}\sqrt{\frac{6\cdot \ln (F_1\cdot F_2\dots F_n)}{\ln(\mbox{lcm}(F_1,\dots,F_n))}},\qquad\qquad\qquad\qquad(1)$$ where $\mbox{lcm}$ denotes the least common multiple.

$$\pi=4\ \sum\limits_{k=1}^{\infty} \arctan{(1/F_{2n+1})}\qquad\qquad\qquad\qquad\qquad\quad(2)$$

$(1)$ admits a mostly elementary proof which relies on the standard properties of Euler's totient function. $(2)$ is almost trivial; it follows from the identity $$\arctan{(1/F_{2n+1})}=\arctan{(1/F_{2n})}-\arctan{(1/F_{2n+2})}.$$

The relations can be found in "A new formula for $\pi$" by Matiyasevich and Guy (Amer. Math. Monthly 93 (1986), 631–635).

-

A small improvement to your question would be to insist that if $x_i=1$ then $x_{i+1}=0$ and to ask for uniqueness. Also, you can generate lots of nice questions by noting that the powers of the 2-by-2 matrix with first row 11 and second row 10 give you matrices with first row $F_{n+1}, F_n$ and second row $F_n,F_{n-1}$. You could ask them to prove that by induction and then deduce consequences such as $F_n^2-F_{n+1}F_{n-1}=\pm 1$. Or you could ask just for the consequences and see what proofs they come up with (inductive arguments are possible). I'm not sure what level of difficulty you are looking for, but these are nice facts.

-
 This is very much in line with the cat map paper commented above, which takes this matrix and does more with it than Knuth does. – Steve Huntsman Jan 15 2010 at 18:05 Thanks! This is a good source of questions. – Donald Jan 15 2010 at 18:13

1) For every natural n exists such natural k>0, that $n|F_k$

2) Consider all pairs of natural numbers $x,y\le n$. Then, the worst-case for Euclid's algorithm for GCD is a pair $(F_{k-1}, F_k)$, where $F_k$ - the biggest Fibonucci number, which doesn't exceed n.

Update: There is a book Fibonacci Numbers by Vorobyev, may be it would be helpful. Matiyasevich used some facts about Fibonacci numbers from this book in his solution of Hilbert's tenth problem.

-
The second result is known as Lame's theorem: mathworld.wolfram.com/LamesTheorem.html – Qiaochu Yuan Jan 15 2010 at 18:37
... by virtue of measuring the lameness of the Euclidean algorithm. (SCNR.) – darij grinberg Nov 22 2010 at 21:55

For undergraduates who know some probability theory, two interesting papers are http://front.math.ucdavis.edu/1008.3202 and http://front.math.ucdavis.edu/1008.3204. These papers concern statistical properties of the number of summands when writing an integer as a sum of nonconsecutive Fibonacci numbers, and generalizations to other sequences of numbers. All but one of the authors of these papers were undergraduates when they wrote the papers.

-

If you do not like your own example, then you may not like this one either, but some of your students might find it interesting. I discovered it along with Roger House when he was an undergraduate.

Let F1 be the 1x1 matrix 1, and create by augmentation 0-1 matrices of larger dimension as follows: (I love < PRE > tags!)

         1 1 0 0 ... 0
0
1                                1 1 0 0
F_(n+1)= .    F_n                         0 1 1 0
.                   1 1          1 0 1 1
.             , so  0 1 is F_2,  0 1 0 1 is F_4, and so on. 

Then det(F_n) = fib(n), which is easy. What is a little harder is that you can toggle the bits of F_n to get a 0-1 matrix with determinant k, for any prescribed k with 0 <= k <= fib(n).

Miodrag Zivkovic liked a similar example enough to include it in his paper at http://arXiv.org/abs/math.CO/0511636 . You might check out his paper to see if that example is the sort of thing for your students.

-

The following exercise seems to be of the type you're looking for.

Let $F(x)$ be the ordinary generating function for the Fibonacci sequence, i.e., $$F(x) = \sum_{n=0}^\infty f_nx^n = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \cdots$$ Show that for all $n \geq 0$, the $n$-th Fibonacci number $f_n$ is equal to $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right].$$

Depending on the abilities of your students, you may want to give them some guidance by first asking them to show that $F(x) = 1/(1-x-x^2)$. The following hint might also be useful: $1 - x - x^2 = \left(1 - \frac{1+\sqrt{5}}{2}x\right)\left(1 - \frac{1-\sqrt{5}}{2}x\right).$

-
 I think it's easier to show this using the recurrence equation for $f_n$. – J.C. Ottem Nov 19 2010 at 22:48 @Ottem - Using power series you can rediscover this result. I don't see how you would come across the result using the definition of $f_n$ directly...? – Sam Nead Dec 5 2010 at 17:14 @Sam: it's a linear recurrence relation of order 2, so you check the root of the "characteristic equation" and that is enough to express the general term explicitly up to two coefficients... solve a small 2x2 system for the two coefficients and you have everything. Of course, that recipe hides the power series, but it can be proved rather easily without invoking them just by using the induction principle. In France, first year students (in maths) get the recipe with an induction proof, and second years get to generalize to higher order linear recurrence relations using power series. – Julien Puydt Sep 28 at 5:40 @Sam even better than my comment: en.wikipedia.org/wiki/… – Julien Puydt Sep 28 at 5:41

My favorite identities are the formulae $$F_{n+1}=\sum_{2k\le{n}}{n-k\choose k}\ =\sum_{i\in\mathbb{Z}}(-1)^i {n\choose{\lfloor {(n+5i)}/2\rfloor}}$$ and $$F_{n}=\sum_{2k\le{n-1}}{n-1-k\choose k}\ =\sum_{i\in\mathbb{Z}}(-1)^i {n\choose{\lfloor {(n+5i-1)}/2\rfloor}}$$. They have been found by I. Schur in 1917. In fact he has proved a q-analogue which immediately implies the Rogers-Ramanujan identities.

-
What's the $q$-analog of $F_n$? – Mariano Suárez-Alvarez Feb 19 2012 at 3:00
The $q-$analogues are: Define the $q-$Fibonacci polynomials $F_n(t)$ by $$\sum_{j = 0}^{\left\lfloor {(n-1)/2} \right\rfloor } {q^{j^2}}{n-j-1\brack j} t^{j}.$$ Then $$F_{n+1}(1)= \sum_{i\in\mathbb{Z}}(-1)^i q^{\frac{i(5i-1)}{2}} {{n\brack{\lfloor {(n+5i)}/2\rfloor}}}$$ and $$F_{n}(q)= \sum_{i\in\mathbb{Z}}(-1)^i q^{\frac{i(5i-3)}{2}} {{n\brack{\lfloor {(n+5i-1)}/2\rfloor}}}.$$ – Johann Cigler Feb 20 2012 at 12:04

1. Thomas Koshy's near-encyclopedic text Fibonacci and Lucas Numbers with Applications contains many, many results on Fibonacci numbers, many of which can be proved using techniques available to undergraduates.

2. As a variant on gowers' answer about taking powers of the matrix

    1 1
1 0


I wrote a paper a few years ago on using the determinant sum property and this matrix to prove some Fibonacci identities. It appeared in The College Mathematics Journal and is very much at the undergraduate level.

-

Here is my favorite: the Zeckendorf family identities (by Philip Matchett Wood and Doron Zeilberger).

Every sufficiently high (= high enough for the right hand sides to make sense) integer $n$ satisfies

$1f_n=f_n$;

$2f_n=f_{n-2}+f_{n+1}$;

$3f_n=f_{n-2}+f_{n+2}$;

$4f_n=f_{n-2}+f_n+f_{n+2}$;

$5f_n=f_{n-4}+f_{n-1}+f_{n+3}$;

etc.

The pattern behind these identities is: $kf_n$ on the left, a sum of $f_{n+\alpha}$ on the right, where no $\alpha$ occurs twice, and no two consecutive integers both occur as $\alpha$'s.

It turns out that such an identity is unique for all $k$.

(Shameless plug:) It generalizes.

-
"Every sufficiently high (= high enough for the right hand sides to make sense)" - is this remark necessary? Because Fibonacci numbers could be defined for negative $n$. – Nurdin Takenov Nov 22 2010 at 20:50
If you define them correctly (i. e., by following the recurrence back) then it is unnecessary. – darij grinberg Nov 22 2010 at 21:36
How else would you define them? (That is, unlike binomial coefficients there aren't two different plausible interpretations here.) – JBL Nov 22 2010 at 23:08
OK, I was overcautious here, after the mess with binomial coefficients... – darij grinberg Nov 23 2010 at 9:07

Here's one that comes up in the analysis of Fibonacci heaps, a data structure in computer science for keeping track of the minimum of a set of items. However, you don't have to know any computer science to understand the analysis:

Suppose that a dynamic forest of rooted trees undergoes two types of change:

• If the roots of two trees have the same number of children, they may merge by making one root be a child of the other.
• Certain tree edges may be removed, causing the child node of the edge to be promoted to become the root of a separate tree. However, during any period of time in which any node x is not itself the root of one of the trees, at most one of the children of x can be removed in this way.

Prove that, in the resulting forest, every node with n children has at least $F_n$ nodes (including itself) in its subtree, where $F_n$ is the $n$th Fibonacci number.

The recurrence $$F_n = 2 +\sum_{i=0}^{n-2} F_i$$ (for $n>0$) that one gets as part of the proof is not the standard recurrence for the Fibonacci numbers but has the same solution as may easily be shown by induction.

-

A connection to divergent summation.

Fist I was much surprised that the alternating sum of all fibonacci-numbers came out to be

$1-1+2-3+... = 1 \text{ {Euler-summation} }$

But well, sometimes things are easy, so why not. But the non-alternating sum is usually much more difficult to access. But nope:

$1+1+2+3+5+8+... = -1 \text{ {matrix-sum}}$

by a matrix-approach, simply. There was a thread in the newsgroup sci.math recently where this was also shown. Discussion of this is at Rob Johnson's site - finally this can be shown using the Binet-form of the fibonacci-numbers and considering the geometric series, which result if all that fibonacci-numbers in their Binet-representation are summed.

Once I've experimented with the (divergent) sum of the bernoulli-numbers, weighted by the fibonacci-numbers. I could not yet prove it, but I arrived at the very likely result that that sum is zero (See pg.11 of Bernoulli/Fib)

-

The International Mathematics Olympiad of 1981 included the following as the final problem of Day 1:

Determine the maximum value of $m^2+n^2$, where $m$ and $n$ are integers satisfying $m,n \in \lbrace 1,2,\ldots,1981\rbrace$ and $(n^2-mn-m^2)^2 = 1$.

[1981 was one of the two IMO's I participated in. I first solved this using standard Pell-equation machinery, but recognized the maximal solution $(987,1597)$ and then wrote up a solution along the intended lines.]

-

I am rather partial (baised) to a paper my thesis advisor and I wrote. It can be found at http://www.tylerclark12.com/Portfolio/Math/FibQuarterly.pdf. You may not be able to use all of the contents of the paper for your class, but I am sure you could use some of it. Let me know if I can be of any further assistance.

-

A very simple yet interesting identity is

$$f_{n+1} = \left[ \frac{1+\sqrt{5}}{2} f_n \right] ; n > > 0 \,.$$

where $[ \; ]$ denotes the closest integer. If I remember right this equality holds for all $n >5$; and in general is true for all recurrences for which the lasrgest eigenvalue is a Pisot number.

-

Consecutive Fibonacci numbers result in the maximum number of iterations in Euclid's GCD algorithm compared with all smaller pairs.

-
 Sorry missed the other similar answer. – Mark Biggar Apr 8 2010 at 21:44