Editing Fibonacci sequence (section)

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