56
$\begingroup$

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?

$\endgroup$
11
  • 2
    $\begingroup$ You might be interested in Dyson and Falk's paper "Period of a Discrete Cat Mapping" at jstor.org/pss/2324989 $\endgroup$ Jan 15, 2010 at 17:55
  • 9
    $\begingroup$ For a whole raft of such questions, see 1.2.8 of Knuth's The Art of Computer Programming, vol. 1. $\endgroup$ Jan 15, 2010 at 17:58
  • 11
    $\begingroup$ 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 in a row?) Which type do you have in mind, or are you indifferent? $\endgroup$ Jan 15, 2010 at 18:11
  • 2
    $\begingroup$ I like your example. What's not so good about it? $\endgroup$
    – Dan Piponi
    Jan 15, 2010 at 18:26
  • 5
    $\begingroup$ It's probably too 'researchy' for an undergrad course, but Florian Luca has a fantastic proof that no Fibonacci number is a perfect number (i.e. a number n such that sigma(n)=2n). You can read the paper here: springerlink.com/content/808137547w5621p7/fulltext.pdf $\endgroup$
    – user1073
    Jan 15, 2010 at 18:38

28 Answers 28

38
$\begingroup$

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:

enter image description here

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

$\endgroup$
8
  • 5
    $\begingroup$ That sounds like a lot of fun. I might assign this as homework the next time I teach undergraduate number theory. $\endgroup$ Jan 15, 2010 at 18:22
  • 13
    $\begingroup$ Induction? Bah! It's a direct corollary of the combinatorial definition of the Fibonacci numbers in terms of tilings using 1x1 and 1x2 tiles. $\endgroup$ Jan 15, 2010 at 18:38
  • 12
    $\begingroup$ 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. $\endgroup$ Jan 15, 2010 at 18:42
  • 7
    $\begingroup$ 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.$$ $\endgroup$ Nov 19, 2010 at 17:09
  • 19
    $\begingroup$ 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. $\endgroup$ Feb 19, 2012 at 0:13
52
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 17, 2010 at 1:06
  • 4
    $\begingroup$ These are very striking results. Already I find 1) very surprising! $\endgroup$ Apr 9, 2010 at 4:04
  • 1
    $\begingroup$ 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 ... $\endgroup$ Nov 22, 2010 at 21:42
  • $\begingroup$ ... smaller by means of jumping from one rational solution to another via Vieta). $\endgroup$ Nov 22, 2010 at 21:42
  • $\begingroup$ Sorry, I meant $\frac15\left(\left(\frac{a}{2}\right)^2\pm 1\right)$. $\endgroup$ Nov 22, 2010 at 21:44
26
$\begingroup$

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.

$\endgroup$
3
  • 16
    $\begingroup$ 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. $\endgroup$ Jan 18, 2010 at 10:53
  • 7
    $\begingroup$ I'd always thought that was a famous and obviously impossible open problem ... $\endgroup$
    – gowers
    Nov 19, 2010 at 16:31
  • 5
    $\begingroup$ You were dead right too, until a couple of years ago. The proof uses Wiles' machinery and transcendence methods. $\endgroup$ Nov 19, 2010 at 19:27
24
$\begingroup$

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!"

$\endgroup$
22
$\begingroup$

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).

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Another neat connection between Fibonacci numbers and tilings: the Fibonomial coefficients! en.wikipedia.org/wiki/Fibonomial_coefficient math.hmc.edu/~benjamin/papers/Fibonomial.pdf $\endgroup$ Jan 15, 2010 at 19:26
  • $\begingroup$ 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/Challenges/…). The site provides a rough solution in the asymptotic regime but the exact expression would involve Fibonacci numbers. $\endgroup$
    – Dinesh
    Apr 8, 2010 at 18:41
  • $\begingroup$ 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 ... $\endgroup$ Nov 22, 2010 at 21:53
  • $\begingroup$ ... 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. $\endgroup$ Nov 22, 2010 at 21:54
  • $\begingroup$ @darij: indeed. Perhaps you might be interested in helping me solve this math.SE problem: math.stackexchange.com/questions/2483/… $\endgroup$ Nov 22, 2010 at 22:27
11
$\begingroup$

For undergraduates who know some probability theory, two interesting papers are https://arxiv.org/abs/1008.3202 and https://arxiv.org/abs/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.

$\endgroup$
10
$\begingroup$

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.]

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ "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$. $\endgroup$ Nov 22, 2010 at 20:50
  • $\begingroup$ If you define them correctly (i. e., by following the recurrence back) then it is unnecessary. $\endgroup$ Nov 22, 2010 at 21:36
  • 2
    $\begingroup$ How else would you define them? (That is, unlike binomial coefficients there aren't two different plausible interpretations here.) $\endgroup$
    – JBL
    Nov 22, 2010 at 23:08
  • $\begingroup$ OK, I was overcautious here, after the mess with binomial coefficients... $\endgroup$ Nov 23, 2010 at 9:07
8
$\begingroup$

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.

$\endgroup$
2
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 15, 2010 at 18:05
  • $\begingroup$ The matrix Tim refers to was called the Q-matrix, and was exploited many times in the heyday of the Fibonacci Quarterly, in the 1960s-1970s. You can view everything online at fq.math.ca. These issues have problem sections (like the Amer. Math. Monthly) and lots of interesting papers an undergraduate could read. $\endgroup$ Apr 30, 2015 at 18:38
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ What's the $q$-analog of $F_n$? $\endgroup$ Feb 19, 2012 at 3:00
  • $\begingroup$ 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}}}.$$ $\endgroup$ Feb 20, 2012 at 12:04
7
$\begingroup$

First, an objection - most of the Fibonacci problems can be generalized to $a_n$-problems where $a_n$ is a sequence satisfying a second order recurrence relation. It's rare (but happens!!) that the Fibonacci recurrence itself is important.

Now I'll present 4 very different problems.

1. Arithmetic of Fibonacci and Carmichael's Theorem

This one is more of a project. The final result is a special case of Carmichael's Theorem: For each $n\neq 1,2,6,12$, the Fibonacci number $F_n$ has a prime divisor not dividing any of the previous Fibonaccis, $\{ F_i \}_{i < n}$ (AKA "a primitive prime divisor").

  • Warm-up: Start by proving $n \mid m \implies F_n \mid F_m$. Improve this to the infamous GCD property: $(F_n,F_m)=F_{(n,m)}$.
  • (Corollary: The product of $m$ consecutive Fibonaccis is divisible by the product of the first $m$ Fibonaccis. Explanation: This is equivalent to the integrality of Fibonomial coefficients, defined as $\binom{n}{m}_F := \frac{n!_F}{m!_F (n-m)!_F}$, where $n!_F := \prod_{i=1}^{n} F_i$. One can prove a Pascal-like identity: $\binom{n}{m}_F \in Span_{\mathbb{Z}}\{\binom{n-1}{m}_F, \binom{n-1}{m-1}_F\}$, and deduce the result by induction.)
  • Primitive Fibonaccis: Prove the existence of positive integers $\{G_n\}_{n \ge 1}$ such that $F_n=\prod_{d\mid n} G_d$ for all $n \in \mathbb{N}$. This sequence is called the "primitive part of Fibonacci". To show that $F_n$ has a primitive prime divisor almost always, it is enough (actually, equivalent) to establish this for $G_n$.
  • Prove that $G_n \ge \varphi^{\varphi(n)} (2\varphi -4)$.
  • Let $n \neq 6$. Show that if $p \mid G_n, G_m$ with $m<n$, then $p^2 \nmid G_n$ and $n$ is of the form $p^r k$ where $k$ is the smallest positive integer such that $p \mid F_k$ and $r \ge 1$.
  • Let $n\neq 6$. Whenever $G_n > \prod_{p \mid n}n$, we deduce $G_n$ has a primitive prime divisor. In the rare few cases it doesn't hold, we must inspect by hand what happens. This gives the special case of Carmichael's Theorem, which is in some sense the hardest. (This step of the proof is somewhat dirty; It is also the last.)
  • Extra: Show that for $n \neq 5$, a primitive prime divisor of $F_n$ must equal $\pm 1 \mod n$. In particular, Carmichael's theorem implies that the greatest prime divisor of $F_n$ tends to infinity with $n$. To establish that $F_n$ has a prime divisor growing faster than $n$, one needs to use the latest results on p-adic logarithmic forms (See the paper "On divisors of Lucas and Lehmer numbers" by C. L. Stewart).

2. Guess-The-Number Game

Alice chooses an integer in $\{ 1, 2,\cdots ,n \}$, and Bob has to find the number using Yes\No questions. Each question costs Bob money: If the answer is positive, he pays $1 \$$. If the answer is negative, he pays twice this amount - $2\$$.

What is the minimal amount of money Bob must have to ensure he can find out Alice's number?

(Does someone have a reference for this game? It was told to me too long ago.)

3. Fibonacci Algorithm

Devise an algorithm that verifies any reasonable Fibonacci identity. (Discussed in the first chapter of "A=B". The sequences $(F_n,L_n)$ has the same role as $(\cos x,\sin x)$ has in trig identities).

4. Crazy Lucas Congruence

Let $L_n:=F_{n-1}+F_{n+1}$. Prove that $p^n \mid L_{p^n} - L_{p^{n-1}}$ for any prime $p$ and any $n \ge 1$.

More generally: $\forall n \in \mathbb{N}:\sum_{d \mid n} L_d \mu(n/d) \equiv 0 \mod n$.

This admits a combinatorial proof, as well as proofs coming from symmetric functions and $p$-adic numbers. See chapter 7 in "A Course in p-adic Analysis" by Alain M. Robert (page 410) and this paper. It is instructive to learn\find the different proofs.

$\endgroup$
7
$\begingroup$

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 $F_1$ 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
F_(n+1)= 0    F_n                         1 1 0 0
         0                                0 1 1 0
         :                   1 1          1 0 1 1
         0             , 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 \le k \le 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.

Gerhard "Ask Me About System Design" Paseman, 2010.01.15

$\endgroup$
7
$\begingroup$

The reciprocals of the Fibonacci numbers $F_2 = 1$, $F_4 = 3$, $F_8 = 21$, $F_{16} = 987$, $F_{32} = 2178309$, . . . of power-of-two order can be summed in closed form: $$ \sum_{n=1}^\infty \frac1{F_{2^n}} = \frac{5 - \sqrt{5}}{2} \, . $$ More generally, $$ \sum_{n=1}^\infty \frac1{F_{2^n k}} = \frac{\sqrt{5}}{\varphi^{2k}-1} $$ ($k=1,2,3,\ldots$); comparing the sums for $k$ and $2k$ yields the proof by telescoping sum.

(This is a special case of a formula that turned up recently in a Math Stackexchange question, which refers to an earlier question nin which Jeffrey Shallit wrote that the $k=1$ formula is "known", but with no further reference [his answer cites Salzer's paper in the 1947 Monthly, which however does not contain this $(5-\sqrt5)/2$ formula]; this looks like the kind of result that's much easier to derive than to locate in the literature.)

$\endgroup$
2
  • $\begingroup$ The second equation relates the golden ratio with its approximations $\dfrac{F_{2n+1}}{F_{2n}}$. This MSE question asks for $\dfrac{F_{2n+2}}{F_{2n+1}}$. $\endgroup$ Jun 4, 2017 at 19:57
  • 2
    $\begingroup$ The Fibonacci formula can be found, for example, in I. J. GOOD,A reciprocal series of Fibonacci numbers. Fibonacci Quart. 12, 346 (1974) and V. E. HOGGATT, Jr. and M. BICKNELL,A reciprocal series of Fibonacci numbers with subscripts 2^n k. Fibonacci Quart. 14, 453-455 (1976), but I think it actually goes back to the 19th century. $\endgroup$ Nov 24, 2019 at 20:22
5
$\begingroup$

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).$

$\endgroup$
4
  • 1
    $\begingroup$ I think it's easier to show this using the recurrence equation for $f_n$. $\endgroup$
    – J.C. Ottem
    Nov 19, 2010 at 22:48
  • $\begingroup$ @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...? $\endgroup$
    – Sam Nead
    Dec 5, 2010 at 17:14
  • $\begingroup$ @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. $\endgroup$ Sep 28, 2012 at 5:40
  • $\begingroup$ @Sam even better than my comment: en.wikipedia.org/wiki/… $\endgroup$ Sep 28, 2012 at 5:41
5
$\begingroup$

Two answers:

  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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This should say $1+\sum_{i=0}^{n-2}F_i$, presumably. $\endgroup$ Apr 30, 2015 at 7:47
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Sorry missed the other similar answer. $\endgroup$ Apr 8, 2010 at 21:44
4
$\begingroup$

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)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$
  1. Parametrization of the equation $x^2-xy-y^2=\pm1$. Next step is a 2-dmensional isolation theorem, see Cassels, J. W. S. An introduction to the geometry of numbers, sec. II. 4. Indefinite quadratic forms.

  2. Wythoff's game.

  3. Another good game is Fibonacci nim.

  4. Newton's method applied to $x^2-x-1=0$ with $x_0=0$ or $x_0=1.$

  5. For odd $p$ we have $F_n\left(U_{p-1}\left(\frac{\sqrt{5}}{2}\right)\right)=\frac{F_{np}}{F_p}$, where $F_n(x)$ and $U_n(x)$ are Fibonacci and Tchebyshev polynomals.

  6. Nice continued fraction (see formula (6.143) from Concrete mathematics) $$\frac{z^{F_1}}{1+\frac{z^{F_2}}{1+\frac{z^{F_3}}{1+\frac{z^{F_4}}{1+\ldots}}}}=(1-z)\sum_{n\ge 1}z^{[n\varphi]}.$$

$\endgroup$
1
  • $\begingroup$ Regarding 1, also fun to note that that fact is a critical step in Matiyasevich's resolution of Hilbert's Tenth Problem. $\endgroup$
    – JoshuaZ
    Oct 10, 2021 at 23:54
2
$\begingroup$

This is a generalization of the classical Fibonacci numbers which opens up many many facets of inherited properties. Define $\{0\}_{s,t}=0, \{1\}_{s,t}=1$ and for $n\geq2$, $$\{n\}_{s,t}=s\{n-1\}_{s,t}+t\{n-2\}_{s,t}.$$ Here $s$ and $t$ may be treated either as variables or numbers. For simplicity, write $\{n\}$ for $\{n\}_{s,t}$. The first few values are: $$\{2\} = s, \qquad \{3\} = s^2 + t, \qquad \{4\}= s^3 + 2st, \qquad \{5\} = s^4 + 3s^2t + t^2.$$ If $s=2, t=-1$ then $\{n\}=n$ the usual integers. If $s=q+1, t=-q$, we get the standard $q$-analogues of integers $$\{n\}=1+q+\cdots+q^{n-1}=[n]_q.$$ After these introductions, then several classical results generalize. For example (see Corollary 2.6 in the reference below for a probabilistic proof) $$\sum_{n=0}^{\infty}\frac{t\{n\}_{s,t}}{(s+t)^{n+1}}=\frac1{s+t-1}$$ generalizes (put $s=t=1$) $$\sum_{n=0}^{\infty}\frac{F_n}{2^{n+1}}=1.$$ You may choose and pick additional results from http://arxiv.org/pdf/1306.6511.pdf

$\endgroup$
1
$\begingroup$

$\bullet~~$ If $x^2=x+1$ ,$n\ge 2$ then we have $x^n=F_nx+F_{n-1}$, where $F_n$ is the $n^{th}$ Fibonacci number.

$\bullet~~\sum_{i=2}^{n} \tau^i+(1-\tau)^i =3(F_{n+1}-1)$ where $F_n$ is the $n$th Fibonacci number and $\tau$ is the Golden ratio. It follows from the identity stated in the post by David.

Here you can get a full proof for both.

$\bullet~~$ Recently I found a generalized version for Cesaro theorem [theorem no. 81] in Fibonacci numbers. It states that - for fixed $p$,$$\sum_{k=1}^{n}\dbinom{n}{k}F_p^kF_{p-1}^{n-k}F_k=F_{pn}.$$ You can get a full proof in Issue 3, Mathematical Reflections, 2018 (page 16).

$\endgroup$
0
$\begingroup$

"A combinatorial proof for the non-recursive expression of the Fibonacci polynomial"

One of the well-known extension of the Fibonacci sequence is the Fibonacci polynomial which is defined by the following recurrence relation $$ F_n(x)=xF_{n-1}(x)+F_{n-2}(x)\, . $$ A non-recursive expression for $F_n(x)$, given in the following form

$$ F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ j \end{array} \right) x^{n-2j-1} \, . $$ Now, i want to prove the above formula with the combinatorial method. Assume the following matrix $$ A_2=\left( \begin{array}{cc} x & 1 \\ 1 & 0 \end{array} \right) \, . $$ With the induction on $n$, we can prove that the $n$th power of the matrix $A_2$ is as follows $$ A_2^n=\left( \begin{array}{cc} F_{n+1}(x) & F_{n}(x) \\ \\ F_{n}(x) & F_{n-1}(x) \end{array} \right) \, . $$ Assume the matrix $A_p$ of order $p$, be in the following form

$$ A_p=\left( \begin{array}{cccccc} u_1 &u_2 &\cdots& \cdots &u_{p-1} &u_p \\ 1 &0 &\cdots &\cdots &\cdots &0 \\ 0 &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ 0 &\cdots &\cdots &0 &1 &0 \\ \end{array} \right)_{p \times p} \, . $$ We have the following combinatorial theorem by Chen about the $(i,j)$ entry of the $n$th power of matrix $A_p$, as shown

Let the $(i,j)$ entry of the $n$th power of matrix $A_p$ called $a_{ij}^n$, then the combinatorial closed-form of $a_{ij}^n$, is in the following form $$ a_{ij}^n=\sum_{(k_1,k_2,\cdots,k_p)} \frac{k_j+k_{j+1}+\cdots+k_p}{k_1+k_2+\cdots+k_p}\times \left( \begin{array}{c} k_1+\cdots+k_p \\ k_1,\cdots , k_p \end{array} \right) u_1^{k_1}\cdots u_p^{k_p} \, . $$ where the summation is over non-negative integers satisfying $$ k_1+2\, k_2+3\, k_3+\cdots + p\, k_p=n-i+j \, . $$ and the coefficients $k_i$ are defined $1$ when $n=i-j$. $$

Based on the Chen theorem the combinatorial closed-form of $F_n(x)$, is in the following form(notice that to the position of $F_n(x)$ in the matrix $A_2^n$)

$$ F_n(x)=\sum_{(k_1,k_2)} \left( \begin{array}{c} k_1+k_2 \\ k_1, k_2 \end{array} \right) x^{k_1} \, . $$

where the summation is over non-negative integers satisfying $$ k_1+2\, k_2=n-1\, . $$

from the last relation, we get the two following equations

$$ k_1+2\, k_2=n-1 \quad \Longrightarrow \left\{ \begin{array}{cc} 1) & k_1+k_2=n-k_2-1 \, ,\\ \\ 2) & k_1=n-2k_2-1 \, . \end{array} \right. $$

using the two above equations, we have

$$ F_n(x)=\sum_{k_2} \left( \begin{array}{c} n-k_2-1 \\ n-2k_2-1, k_2 \end{array} \right) x^{n-2k_2-1} \, . $$

for simplicity, denote $k_2$ by $j$, then we rewrite the above relation, as follows

$$ F_n(x)= \sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ n-2j-1 , j \end{array} \right) x^{n-2j-1} =\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \left( \begin{array}{c} n-j-1 \\ j \end{array} \right) x^{n-2j-1} \, . $$

Chen article: http://www.sciencedirect.com/science/article/pii/0024379595901639

$\endgroup$
0
$\begingroup$

Table 2 and the proof in Proposition 1 in this paper is quite cool - they show that the Fibonacci numbers appear quite nicely when studying the Collatz sequence.

Basically, the number of permutations of length $n$ obtained from length-$n$ subsequences are at least Fibonacci $n$, with equality for $n \leq 14$ (!)

$\endgroup$
0
$\begingroup$

Ask them to prove that the ratios of the Fibonacci sequence tends to the golden ratio. That is $\frac{F_n}{F_{n-1}} \to \phi$. This can be done with basic calculus.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.