Undesrstanding a proof related to Fibonacci numbers.

I was going through the following proof of the book Introductory Combinatorics by Richard A. Brualdi.

Theorem. The Fibonacci numbers satisfy the formula

$$f_n = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$$

My doubt: In the proof they have written that we consider the Fibonacci recurrence relation in the form

$$f_n - f_{n-1} - f_{n-2} = 0$$

One way to solve this recurrence relation is to look for a solution of the form $$f_n =q^n$$, where q is a nonzero number.

How and why we consider the solution of the form $$f_n =q^n$$? Maybe I am missing something very basic here. Unable to recall. The rest of the proof was understandable. Kindly help in this regard. Thank you so much for the help.

• Why we consider solutions of the form $q^n$ is because they work. There is a history question of how somebody found that they work, but that is not math. It is not an unreasonable thing to try. Once we consider them we can prove they work easily, which you have accepted. The other question is how we know there are not other solutions. To me, that depends on the linear algebra proof that solutions to a linear homogenous equation form a vector space, then finding the dimension of the space, and noting that we have a basis. – Ross Millikan Jun 18 at 5:04

7 Answers

(This is now a long answer, but you can stop after any section. Each section just takes a different approach, or notes similarities with other types of problems.)

The first time you see this, given the order things are normally taught, it does seem arbitrary. It is clearer when you see how the recurrence plays out either in linear algebra or in generating functions.

You can, of course, prove directly that the formula is true. If $$g_n$$ is the formula, you just need to show $$g_0=0,g_1=1,$$ and $$g_{n+1}=g_n+g_{n-1}.$$

But that isn’t a satisfying reason for why it takes this form.

If we define a generating function: $$g(x)=\sum_{k=0}^{\infty} f_kx^k.$$ Then the recurrence means that we get: $$g(x)(1-x-x^2)=f_0+(f_1-f_0)x=x$$ or:

$$g(x)=\frac{x}{1-x-x^2}$$

Then using partial fractions, from calculus, you get, if $$r_1,r_2$$ are the roots of $$y^2-y-1=0,$$ then for some $$a_1,a_2$$:

\begin{align}\frac{x}{1-x-x^2}&=\frac{a_1}{1-r_1x}+\frac{a_2}{1-r_2x}\\&=\sum_{k=0}^{\infty}(a_1r_1^k+a_2r_2^k)x^k.\end{align}

As is usual with partial fractions, if the polynomial in the denominator has repeated roots, then your general term is, if the degree of a root $$r_i$$ in the polynomial is $$d_i,$$ $$\frac{a_{k,i}}{(1-r_ix)^k}\quad\quad1\leq k\leq d_i.\tag1$$ You have to learn to expand (1) as a power series.

The linear algebra approach is to note:

$$\begin{pmatrix}f_{n+1}\\f_{n}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f_{n}\\f_{n-1}\end{pmatrix}$$

So if $$A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$$ you have: $$\begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=A^n\begin{pmatrix}f_{1}\\f_{0}\end{pmatrix}$$

The matrix $$A$$ has characteristic polynomial $$x^2-x-1,$$ which has two distinct roots, so there is a matrix $$S$$ so that: $$A=S\begin{pmatrix}r_1&0\\0&r_2\end{pmatrix}S^{-1}$$ and thus $$A^n=S\begin{pmatrix}r_1^n&0\\0&r_2^n\end{pmatrix}S^{-1}$$

So we can express the entries of $$A^n$$ each as $$a_{ij}r_1^{n}+b_{ij}r_2^n,$$ and thus similarly for $$f_n.$$

As with partial fractions, the form of the matrix you get when the polynomial has repeated roots gets more complicated. You can't get a diagonal matrix, in general, only a matrix in Jordan Normal Form.

A third way to think of it is in terms the vector space of all sequences $$\mathbf a=(a_i)_{i=0}^\infty$$ and the linear operator:

$$D\mathbf a =(a_{i+1})_{i=0}^\infty$$

Then our recurrence means that if $$\mathbf f=(f_i)$$ then $$(D^2-D-I)\mathbf f=0,$$ here $$I$$ is the identity operator $$I\mathbf a=\mathbf a.$$

Rewriting that as:

$$(D-r_1I)(D-r_2I)\mathbf f=0$$

Then let $$\mathbf e=(D-r_2I)\mathbf f=(f_{i+1}-r_2f_i)_i$$

Then since $$(D-r_1I)\mathbf e =0$$, you get that $$e_i=r_1^ie_0.$$

Similarly, $$d_i=f_{i+1}-r_1f_i$$ gives $$d_i=r_2^id_0,$$ so $$d_i+e_i=2f_{i+1}-(r_1+r_2)f_i=2f_{i+1}-f{i}$$

So $$\mathbf d+\mathbf e =(2D-1)\mathbf f.$$

Then use that $$(2D-1)(2D-1)-4(D^2-D-1)=5\tag 2$$ then:

$$(2D-1)(\mathbf d +\mathbf e)=(2D-1)(2D-1)\mathbf f=5\mathbf f$$

And $$2d_{i+1}-d_i=(2r_2-1)d_0r_2^i,2e_{i+1}-e_i=(2r_1-1)e_0r_1^i$$

And therefore, letting $$c_1=e_0,c_2=d_0,$$ you get: $$f_i=\sum_{j=1}^2\frac{(2r_j-1)}{5}c_jr_j^i.$$

Given $$r_i=\frac{1\pm\sqrt 5}{2},$$ $$2r_i-1=\pm\sqrt 5$$ and $$d_0=e_0=1,$$ you get:

$$f_i=\frac{\sqrt 5}5\left(\frac{1+\sqrt 5}2\right)^i -\frac{\sqrt 5}5\left(\frac{1-\sqrt 5}2\right)^i$$

In the more general case, if $$p(x)$$ is a polynomial with no repeated root, then $$\gcd(p(x),p’(x))=1.$$ (In the case of Fibonacci, $$p(x)=x^2-x-1$$ and $$p’(x)=2x-1.$$) Then:

$$p’(x)=\sum p_j(x)$$ where $$p_j(x)=\frac{p(x)}{x-r_j}$$ where the $$r_i$$ are the roots of $$p.$$

Then if $$p(D)\mathbf a=0,$$ you get $$p_j(D)\mathbf a$$ is a geometric series with common ratio $$r_j,$$ and $$p’(D)\mathbf a = (\sum c_jr_j^i)$$

But the GCD requirement means we have a solution to:

$$u(x)p’(x)+v(x)p(x)=1\tag3$$

(In Fibonacci, $$u(x)=(2x-1)/5, v(x)=4/5,$$ by (2).)

So this mean:

$$u(D)p’(D)\mathbf a = \mathbf a$$

And this will give you:

$$a_n=\sum_j c_j u(r_j)r_j^n$$

This technique works up until (3) with repeated roots, except you get $$p’(x)=\sum_j d_ip_i(x).$$ But in (3), the best you can get is:

$$u(x)p’(x)+v(x)p(x)=\prod_{j}(x-r_j)^{d_j-1}$$ So again, repeated roots are a problem.

That last approach is related to linear differential equation, where you are often taught first, “Hey, let’s just try the certain solutions of the form $$e^{rx},$$” without much motivation.

In the vector space of infinitely differentiable functions, we get a linear operator $$D$$ defined as $$Df=f’=\frac{df}{dx}.$$

Then linear differential equations can be written as $$p(D)f=0$$ for some polynomial $$p.$$

As before, if $$p(x)$$ has no repeated roots, you get: $$g_i=p_i(D)f$$ is a root of $$(D-r_i)g_i=0$$ or $$g_i’(x)=r_ig_i(x),$$ which has a known solution set $$g_i(x)=C_ie^{r_ix}.$$

Then $$u(D)p_i(D)f=C_iu(r_i)e^{r_ix}$$ and $$f=u(D)p’(D)f =\sum_{i} C_iu(r_i)e^{r_ix}$$

Essentially, we are finding solutions to $$p(D)f=0$$ in terms of known eigenvectors $$v_i$$ of the linear operator $$D$$ for eigenvalues $$r_i,$$ and it always gets more complicated when there are repeated roots.

Even the linear algebra approach works this way.

$$A$$ satisfies $$p(A)=0,$$ so given any vector $$\mathbf v$$ we get $$\mathbf v_i=p_i(A)\mathbf v$$ is an eigenvectors of $$A$$ for eigenvalue $$r_i.$$

So $$\mathbf v=u(A)p’(A)\mathbf v =\sum u(r_i)\mathbf v_i$$

And:

$$A^n\mathbf v =\sum u(r_i)r_i^n \mathbf v_i.$$

In the Fibonacci case, $$\mathbf v=(1,0)^t$$ and $$\mathbf v_i=(1-r_{3-i},1)^t=(r_i,1)$$ and $$u(r_i)=(2r_i-1)/5=\pm\frac{1}{\sqrt5}.$$.

If you've ever studied differential equations you've probably encountered something similar, where a solution of a certain form is suggested and then found to work. This is no coincidence, since the theories of differential equations and of recurrences have some commonalities. In both settings it is common for students to feel unsatisfied when they first encounter this kind of argumentation.

Some things that may help psychologically:

1. it had to wait a long time before the first human stumbled upon the solution that textbook authors now present so matter-of-factly. I don't know how this particular solution was first found; perhaps somebody came to the problem with some relevant experience, perhaps from having studied differential equations; perhaps there was lot of trial-and-error involved; perhaps they got lucky.
2. there are very similar problems for which this solution method doesn't work, at least not without modification. Consider $$f_n=2f_{n-1}-f_{n-2}$$. The method fails here because the secular equation has a double root. I'm sure Brualdi discusses the modification needed to handle this case, although I don't have the book handy to check this. (It involves positing $$nq^n$$ as a second solution.) The point is that it isn't the case that the guess is so obvious it just has to work. It doesn't have to work, but it is worth trying and happens to be successful.

Now for some possible motivations for making such a guess.

1. This is a two-term recurrence. Perhaps one should try solving one-term recurrences before tackling this. How about $$f_n=3f_{n-1}?$$ This equation just says that each term is $$3$$ times as big as the preceding term, so an exponential solution just pops out: $$f(n)=C\cdot3^n$$. Returning to the two-term case, one might wonder what would happen if you tried this again, but it isn't clear what base of the exponential to try, so we make that a parameter. After a step or two of algebra, you realize that the $$n$$-dependence cancels out, which has got to be a good thing. So we plow ahead to see how far we can get...
2. We've already mentioned differential equations. If you have the differential equation $$f'(x)=kf(x)$$ you may know that $$q^x$$ solves this, where $$q=e^k$$. You may or may not have seen the generalization: $$a_nf^{(n)}(x)+a_{n-1}f^{(n-1)}(x)+\ldots+a_1f'(x)+a_0f(x)=0$$ can be solved by positing $$f(x)=Ce^{kx}$$ and then solving a polynomial equation to find values of $$k$$ that give solutions.
3. if the trick used to handle the double-root case mentioned above seems unmotivated when you come to it, you can investigate how the analogous issue is handled in the differential equations case. The issues surrounding l'Hôpital's rule are relevant here. The point here is that the solution method is tied in with a lot of other mathematics.

I think by considering $$f_n=q^n$$ we get $$f_n-f_{n-1}-f_{n-2}=0 \Rightarrow q^n-q^{n-1}-q^{n-2}=0 \Rightarrow q^n(q^2-q-1)=0$$. Hence by solving the quadratic we can get some idea about $$f_n$$.

• 'yeah, this was easy to get. But my main concern is why we started from $f_n = q^n$ as a solution? – monalisa Jun 18 at 4:21

$$\begin{bmatrix} f_n\\ f_{n-1} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} f_{n-1}\\ f_{n-2} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1}\begin{bmatrix} f_1\\ f_0 \end{bmatrix}$$ Then you can calculate the eigenvalues.

One can find a proof for it here in my paper.
https://www.ssmrmh.ro/2021/04/12/metallic-numbers/
However as an outline note that if $$x^2=x+1 , \text{ then , } x^n = f_n x+f_{n-1}$$ Now note that the only roots of the equation are $$\phi , (1-\phi )$$
Substitute back to get $$\phi ^n =f_n \phi + f_{n-1}$$ $$(1-\phi )^n=f_n(1-\phi) +f_{n-1}$$ Subtracting both equation gives , $$\phi ^n - (1-\phi )^n = f_n (2\phi - 1) = f_n \left( 2\cdot \frac{1+\sqrt{5}}{2}-1\right)$$ This gives $$\phi ^n - (1-\phi )^n=f_n \sqrt{5}$$ Dividing throughout and substitute for $$\phi$$ gives the result $$f_n = \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2}\right)^n -\frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2}\right)^n$$

I thought this approach before and i come to the conclusion such that :

Lets come your question , we said $$f_n=q^n$$ because we know that $$f_n$$ mean ,i.e, represents a number . Moreover ,we can see that any number can be obtained by playing the terms such as $$a \times q^n$$. Thanks to this property , we can satisfy given equations such that $$f_n=f_{n-1} +f_{n-2} +f_{n-3}$$ etc.

More clearly , let say that $$q=2$$ and we also want to obtain some recuresion such as $$f_n=f_{n-1} +f_{n-2} +f_{n-3}$$ , i.e , $$2^n=2^{n-1} + 2^{n-2} +2^{n-3}$$ . We can satify it by some rational number $$a,b,c,d$$ such that $$a2^n=b2^{n-1} + c2^{n-2} +d2^{n-3}$$ . We are also finding these rational numbers by initial conditions

As you understand , thanks to exponentials such as $$q^n$$ , we can satisfy our recursive relation equations.Thans why ,we select them to use.

NOTE = As far as i have understood , you wonder why we choose $$f_n=q^n$$ in the begining. Actually , it can be easly concluded from foregoing explanation. Because , it is obvious that $$f_n$$ is a rational number and we can indicate them by exponential such as $$57 = 57^1$$ or $$1/16 = (1/2)^4$$

The standard approach to work with linear recursive sequences like the Fibonacci sequence is as follows: Let's consider a mapping $$\mathbb{Z}^{+} \mapsto \mathbb{R}$$ where say $$R$$ is an arbitrary ring ,suppose the sequence corresponding to the map is represented as $$\{u_j\}_{\ge 1}^{\infty}$$,

Suppose the recursive relation is of form $$u_{n+k}=\sum_{j=1}^{k}a_{(n+k-j)}\,u_{j}$$ ,where $$a_j \in \mathbb{R}$$

Then to the sequence we can associate a polynomial $$p(\xi ) \in \mathbb{R}[\xi]$$ having the representation

$$p(\xi)=\xi^{k}-\left[\sum_{j=1}^{k}a_j\,\xi^{(k-j)} \right]$$

If $$\{\phi_j:1\le j \le k\}$$ is the zero set of $$p(\xi)$$ with $$\phi_j$$'s being distinct ,then the general term of $$\{u_j\}_{\ge 1}^{\infty}$$ has form

$$u_n =\sum_{j=1}^{k}\phi_j^{n-1} \, \lambda_{j}$$ where $$\lambda_j$$ are constants, which can be computed by explicity computing the first few terms of the series..

NOTE: For a lesiurely yet rigorous account of the theory of linear recursive sequences, I suggest going through the classic soviet text RECURSION SEQUENCES , by Prof Aleksei Ivanovich Markushevich