Summing the Fibonacci Sequence

Left: Fibonacci, or Leonardo of Pisa. Right: Italian postage stamp issued on the 850th anniversary of his birth.

The Fibonacci sequence must be familiar to anyone reading this. We define it by means of a second-order recurrence relation,

$\displaystyle F_{n+1} = F_{n-1} + F_n \,. \ \ \ \ \ (1)$

and two initial values, ${F_0 = 0}$ and ${F_1 = 1}$ . This immediately yields the well-known sequence

$\displaystyle \{F_n\} = \{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots \} \,.$

We can obtain an explicit expression for ${F_n}$ by solving the recurrence relation (1). Seeking a solution of the form ${F_n = \kappa \rho^n}$ , we find two possible values, ${\rho = \phi = (1+\sqrt{5})/2}$ and ${\rho = \psi = (1-\sqrt{5})/2}$ . We recognize ${\phi}$ as the Golden Number. The general solution of (1) is ${F_n = A \phi^n + B \psi^n}$ and, using the initial values, the complete solution is

$\displaystyle F_n = \frac{1}{\sqrt{5}} \biggl [ \phi^n - \psi^n \biggr] \ \ \ \ \ (2)$

This is known as Binet’s Formula, after the French mathematician Jacques Philippe Marie Binet (1786–1856), although it had been found by Abraham de Moivre a century earlier.

Partial Sums of ${\{F_n\}}$ .

The aim now is to find an expression for the partial sums of the sequence:

$\displaystyle S_n := \sum_{k=0}^n F_k \,.$

Clearly, the first few values are easily found:

$\displaystyle \{S_n\} = \{ 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, \dots \} \,.$

By inspection, we see that ${S_n}$ is equal to ${F_{n+2} - 1}$ , at least for the initial terms. We can prove this by means of the recurrence relation (1).

We write the sequence of recurrence relations

$\displaystyle \begin{array}{rcl} F_0 &=& F_2 - F_1 \\ F_1 &=& F_3 - F_2 \\ F_2 &=& F_4 - F_3 \\ \vdots\ &=& \quad\ \ \vdots \\ F_{n} &=& F_{n+2} - F_{n+1} \end{array}$

The sum of the left-hand terms is ${S_n}$ . On the right, all but two of the terms cancel, leaving ${F_{n+2} - F_{1} }$ and bringing us the required result,

$\displaystyle S_n = F_{n+2} - 1 \,. \ \ \ \ \ (3)$

Is this expression of any value?

Mathematics teachers and lecturers are all too familiar with the question “But what use is this?” In the present case, we may well ask if (3) is of practical use. It could be said that, to find ${S_n}$ , we need to know ${F_{n+2}}$ . But this requires ${n+2}$ additions, while direct evaluation of ${S_n}$ requires ${n}$ .

Of course, the worth of (3) lies in its generality. It is not a matter of calculating the terms ${S_n}$ , but in realising that the two sequences, ${\{F_n\}}$ and ${\{S_n\}}$ are so intimately related to each other. From the definition of ${S_n}$ we have ${S_{n+1} = S_{n} + F_{n+1}}$ . Combining this with (3) we get

$\displaystyle S_{n+1} = S_{n-1} + S_{n} + 1 \,. \ \ \ \ \ (4)$

We note that the recurrence relation (4) for ${S_n}$ is an inhomogeneous version of the corresponding relation (1) for ${F_n}$ . It has a particular solution ${S_n \equiv -1}$ . We thus seek a solution

$\displaystyle S_n = C \phi^n + D \psi^n - 1$

and, using the initial conditions, we find ${C=\phi^2/\sqrt{5}}$ and ${D = -\psi^2/\sqrt{5}}$ so that

$\displaystyle S_n = \frac{1}{\sqrt{5}} \biggl [ \phi^{n+2} - \psi^{n+2} \biggr] - 1 \,. \ \ \ \ \ (5)$

This also follows directly from (2) and (3).

Asymptotic Values

Since ${|\phi|>1}$ and ${|\psi|<1}$ , the second terms in (2) and (5) become negligible for large ${n}$ , so that, for large ${n}$ ,

$\displaystyle F_n \approx \phi^n/\sqrt{5} \qquad\mbox{and}\qquad S_n \approx \phi^{n+2}/\sqrt{5} \,.$

The nearest integer gives the exact value for ${F_n}$ ; the nearest integer minus 1 gives the exact value for ${S_n}$ . We may also note that, for large ${n}$ ,

$\displaystyle \frac{F_{n+1}} {F_{n}} \approx \phi \,, \qquad \frac{S_{n+1}} {S_{n}} \approx \phi \,, \qquad \mbox{and}\qquad \frac{S_{n}} {F_{n}} \approx \phi^2 \,.$

So, ${F_n}$ and ${S_n}$ grow exponentially at the same rate, while ${S_n}$ is ${\phi^2}$ times bigger than ${F_n}$ .

Proofs Without Words

In a recent article in The Mathematical Intelligencer (Gryszka, 2022), a “proof without words” for the partial sums of the Fibonacci sequence was presented. It is shown in the figure below. You may find it interesting, although it took me longer to understand it than to find the simple algebraic proof presented above.

Proof without words of the partial sums of the Fibonacci sequence (from Gryszka, 2022).

Sources

${\bullet}$ Karol Gryszka, 2022: Proof Without Words: Sum of Fibonacci Numbers and Beyond. Math. Intelligencer, 44(4), 371–372. M. I. Article.

ThatsMaths