Content deleted Content added
m →Identification: {F_n}^2 puts way too much space between F and 2 |
→Symbolic method: explicit computation of the generating series |
||
Line 363:
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>
Explicitely, if
<math display =block>S=\sum_{i=0}^\infty F_iz^i,</math>
one has
<math display =block>zS=\sum_{i=1}^\infty F_{i-1}z^i,\qquad z^2S=\sum_{i=2}^\infty F_{i-2}z^i.
</math>
So,
<math display =block>S-zS-z^2S= F_0+zF_1-zF_0=z,</math>
which is easy to solve in {{tmath|S}} to get the result.
=== Induction proofs ===
| |||