Nontrivial question about Fibonacci numbers?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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.

Answer 18

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.

Answer 19

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

Answer 20

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)

Answer 21

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.

Answer 22

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.

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

"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

Answer 27

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$ (!)

Answer 28

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.