Editing Fibonacci sequence (section)

== Combinatorial identities ==

=== Combinatorial proofs ===
Most identities involving Fibonacci numbers can be proved using [[combinatorial proof|combinatorial arguments]] using the fact that <math>F_n</math> can be interpreted as the number of (possibly empty) sequences of&nbsp;1s and&nbsp;2s whose sum is <math>n-1</math>. This can be taken as the definition of <math>F_n</math> with the conventions <math>F_0 = 0</math>, meaning no such sequence exists whose sum is&nbsp;−1, and <math>F_1 = 1</math>, meaning the empty sequence "adds up" to 0. In the following, <math>|{...}|</math> is the [[cardinality]] of a [[set (mathematics)|set]]:

: <math>F_0 = 0 = |\{\}|</math>
: <math>F_1 = 1 = |\{()\}|</math>
: <math>F_2 = 1 = |\{(1)\}|</math>
: <math>F_3 = 2 = |\{(1,1),(2)\}|</math>
: <math>F_4 = 3 = |\{(1,1,1),(1,2),(2,1)\}|</math>
: <math>F_5 = 5 = |\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|</math>

In this manner the recurrence relation
<math display=block>F_n = F_{n-1} + F_{n-2}</math>
may be understood by dividing the <math>F_n</math> sequences into two non-overlapping sets where all sequences either begin with 1 or 2:
<math display=block>F_n = |\{(1,...),(1,...),...\}| + |\{(2,...),(2,...),...\}|</math>
Excluding the first element, the remaining terms in each sequence sum to <math>n-2</math> or <math>n-3</math> and the cardinality of each set is <math>F_{n-1}</math> or <math>F_{n-2}</math> giving a total of <math>F_{n-1}+F_{n-2}</math> sequences, showing this is equal to <math>F_n</math>.

In a similar manner it may be shown that the sum of the first Fibonacci numbers up to the {{mvar|n}}-th is equal to the {{math|(''n'' + 2)}}-th Fibonacci number minus&nbsp;1.{{Sfn | Lucas | 1891 | p = 4}}   In symbols:
<math display=block>\sum_{i=1}^n F_i = F_{n+2} - 1</math>

This may be seen by dividing all sequences summing to <math>n+1</math> based on the location of the first 2. Specifically, each set consists of those sequences that start <math>(2,...), (1,2,...), ..., </math> until the last two sets <math>\{(1,1,...,1,2)\}, \{(1,1,...,1)\}</math> each with cardinality 1.

Following the same logic as before, by summing the cardinality of each set we see that
: <math>F_{n+2} = F_n + F_{n-1} + ... + |\{(1,1,...,1,2)\}| + |\{(1,1,...,1)\}|</math>
... where the last two terms have the value <math>F_1 = 1</math>.  From this it follows that <math>\sum_{i=1}^n F_i = F_{n+2}-1</math>.

A similar argument, grouping the sums by the position of the first&nbsp;1 rather than the first&nbsp;2 gives two more identities:
<math display=block>\sum_{i=0}^{n-1} F_{2 i+1} = F_{2 n}</math>
and
<math display=block>\sum_{i=1}^{n} F_{2 i} = F_{2 n+1}-1.</math>
In words, the sum of the first Fibonacci numbers with [[parity (mathematics)|odd]] index up to <math>F_{2 n-1}</math> is the {{math|(2''n'')}}-th Fibonacci number, and the sum of the first Fibonacci numbers with [[parity (mathematics)|even]] index up to <math>F_{2 n}</math> is the {{math|(2''n'' + 1)}}-th Fibonacci number minus&nbsp;1.<ref>{{Citation|title = Fibonacci Numbers |last1 = Vorobiev |first1 = Nikolaĭ Nikolaevich |first2 = Mircea|last2= Martin |publisher = Birkhäuser |year = 2002 |isbn = 978-3-7643-6135-8 |chapter=Chapter 1 |pages = 5–6}}</ref>

A different trick may be used to prove
<math display=block>\sum_{i=1}^n F_i^2 = F_n F_{n+1}</math>
or in words, the sum of the squares of the first Fibonacci numbers up to <math>F_n</math> is the product of the {{mvar|n}}-th and {{math|(''n'' + 1)}}-th Fibonacci numbers. To see this, begin with a Fibonacci rectangle of size <math>F_n \times F_{n+1}</math> and decompose it into squares of size <math>F_n, F_{n-1}, ..., F_1</math>; from this the identity follows by comparing [[area]]s:

[[File:Fibonacci Squares.svg|frameless|260x260px]]

=== Symbolic method ===
The sequence <math>(F_n)_{n\in\mathbb N}</math> is also considered using the [[symbolic method (combinatorics)|symbolic method]].<ref>{{citation |last1=Flajolet |first1=Philippe |last2=Sedgewick |first2=Robert |title=Analytic Combinatorics|title-link= Analytic Combinatorics |date=2009 |publisher=Cambridge University Press |isbn=978-0521898065 |page=42}}</ref> More precisely, this sequence corresponds to a [[specifiable combinatorial class]]. The specification of this sequence is <math>\operatorname{Seq}(\mathcal{Z+Z^2})</math>. Indeed, as stated above, the <math>n</math>-th Fibonacci number equals the number of [[Composition (combinatorics)|combinatorial compositions]] (ordered [[integer partition|partitions]]) of <math>n-1</math> using terms 1 and 2.

It follows that the [[ordinary generating function]] of the Fibonacci sequence, <math>\sum_{i=0}^\infty F_iz^i</math>, is the [[rational function]] <math>\frac{z}{1-z-z^2}.</math>

=== Induction proofs ===
Fibonacci identities often can be easily proved using [[mathematical induction]].

For example, reconsider
<math display=block>\sum_{i=1}^n F_i = F_{n+2} - 1.</math>
Adding <math>F_{n+1}</math> to both sides gives
: <math>\sum_{i=1}^n F_i + F_{n+1} = F_{n+1} + F_{n+2} - 1</math>
and so we have the formula for <math>n+1</math>
<math display=block>\sum_{i=1}^{n+1} F_i = F_{n+3} - 1</math>

Similarly, add <math>{F_{n+1}}^2</math> to both sides of
<math display=block>\sum_{i=1}^n F_i^2 = F_n F_{n+1}</math>
to give
<math display=block>\sum_{i=1}^n F_i^2 + {F_{n+1}}^2 = F_{n+1}\left(F_n + F_{n+1}\right)</math>
<math display=block>\sum_{i=1}^{n+1} F_i^2 = F_{n+1}F_{n+2}</math>

=== Binet formula proofs ===

The Binet formula is
<math display=block>\sqrt5F_n = \varphi^n - \psi^n.</math>
This can be used to prove Fibonacci identities.

For example, to prove that <math display=inline>\sum_{i=1}^n F_i = F_{n+2} - 1</math>
note that the left hand side multiplied by <math>\sqrt5</math> becomes
<math display=block>
\begin{align}
1 +& \varphi + \varphi^2 + \dots + \varphi^n - \left(1 + \psi + \psi^2 + \dots + \psi^n \right)\\
&= \frac{\varphi^{n+1}-1}{\varphi-1} - \frac{\psi^{n+1}-1}{\psi-1}\\
&= \frac{\varphi^{n+1}-1}{-\psi} - \frac{\psi^{n+1}-1}{-\varphi}\\
&= \frac{-\varphi^{n+2}+\varphi + \psi^{n+2}-\psi}{\varphi\psi}\\
&= \varphi^{n+2}-\psi^{n+2}-(\varphi-\psi)\\
&= \sqrt5(F_{n+2}-1)\\
\end{align}</math>
as required, using the facts <math display=inline>\varphi\psi =- 1</math> and <math display=inline>\varphi-\psi=\sqrt5</math> to simplify the equations.