Ułamki i macierze 2-na-2. Tabela Fibonacciego.

· blog
Authors

Definicja tabeli Fibonacciego

Fibonacci znany jest od wieków i na zawsze ze swojego ciągu f(n):

        1 1 2 3 5 8 13 21 34 …

zdefiniowanego rekurencyjnie:

  1. f(1) := f(2) := 1;
  2. f(n) := f(n-1) + f(n-2) dla każdego całkowitego n > 2

Czasem wprowadza się także f(0) := 0. Wzór rekurencyjny 2. powyżej dalej wtedy zachodzi, a nawet dodatkowo dla n=2.

Poniższa tabela uogólnia ciąg Fibonacciego, więc postanowiłem nią uczcić dawnego mistrza. Jest to nieskończona tabela, a tak naprawdę, to jest to nibytabela, bo kolumny są rozmieszczone gęsto, oraz idą w dół, w nieskończoność, przy czym szczyt mają na różnych wysokościach. W każdej kolumnie powtarza się tylko jedna i ta sama liczba (dla różnych kolumn na ogół jest inna). Wartość wyrazów dowolnej kolumny, poza zewnętrznymi, jest sumą wartości najbliższych sąsiednich kolumn, spośród tych które urodziły się wcześniej. Górna część tej tabeli – pierwsze 5 wierszy – wygląda następująco:

[; \begin{array}{ccccccccccccccccc}
1 & & & & & & & & & & & & & & & & 0 \\
1 & & & & & & & & 1 & & & & & & & & 0 \\
1 & & & & 2 & & & & 1 & & & & 1 & & & & 0 \\
1 & & 3 & & 2 & & 3 & & 1 & & 2 & & 1 & & 1 & & 0 \\
1 & 4 & 3 & 5 & 2 & 5 & 3 & 4 & 1 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 0
\end{array} ;]

Definiuje się tę tabelę Fib rekurencyjnie:

  1. Fib(0 0) := 1   oraz   Fib(0 1) := 0;
  2. Fib(h+1   2∙n) := Fib(h n)     dla każdego n=0 … 2h;
  3. Fib(h+1   2∙n – 1) := Fib(h  n-1) + Fib(h n)     dla każdego n=1 … 2h;

dla h=0 1 2 …

Każda kolumna tabeli ma na swoim szczycie nieparzysty indeks poziomy, powiedzmy n, po czym indeks poziomy podwaja się w kolejnych wierszach; kolejne wyrazy kolumny wyglądają następująco:

    F(h n)   F(h+1  2∙n)   F(h+2  4∙n)   F(h+3  8∙n)   …

Oczywiście wszystkie powyższe wyrazy mają tę samą wartość.

Własności tabeli Fibonacciego

Tabela Fibonacciego przypomina fraktal. Gdy usunąć górny wiersz, po czym pozostawić prawą “większą połowę” tabeli, to z powrotem otrzymamy całą tabelę. Formalnie oznacza to:

  • Fib(h+1  2h+n)  =  Fib(h  n)
  • dla każdego h=0 1 … oraz n=0 … 2h. Z tego powodu:

  • Fib(h+1  n)   =   Fib(h+1  2h+n-1)  + Fib(h+1   2h+n)
  • dla każdego h=0 1 … oraz n=0 … 2h.


    Nietrudno dowieść, za pomocą indukcji, że każde dwa kolejne wyrazy dowolnego wiersza tabeli Fibonacciego są względnie pierwsze; co więcej – każda para nieujemnych, względnie pierwszych liczb całkowitych  [;a\ \ b;]  występuje jako kolejne wyrazy w pewnym wierszu (przy tym, poza parą  [;1\ \ 0;], każda występuje w takim wierszu zarówno w danej kolejności, jak i w odwrotnej  [;b\ \ a;] ).


    W tabeli Fibonacciego, najwyższa wartość wyrazu w wierszu h jest liczbą Fibonacciego f(h+1), dla h=0 1 … Poczynając od h=3, występuje ona w takim wierszu dokładnie dwa razy.



    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s

    1. WhoWheWha (in progress)
    2. The sharpest minds ever
    3. California – State – USA – Knol Authors – Knols – Education
    4. Money — economy (part 1)
    5. “california rains”
    6. Pairs, Kuratowski pairs, and reality
    7. Number Theory — congruences
    8. Matematyka – esej
    9. Congruence x^2 ≡ -1 mod p (Euler), and a super-Wilson theorem.
    10. Dabanese – dictionary (1)
    11. Dabanese syntax
    12. Dabanese — a general introduction
    13. Tentative dabanese dictionary (1)
    14. Fractions and diophantine approximations, I
    15. Mathematics — index
    16. Reflections on mathematics (migma)
    17. Special characters & HTML strings
    18. Infinitude of primes – 1
    19. Reference
    20. Geometric progression
    21. Ergänzungssatz: x^2 ≡ 2 mod p; and more.
    22. Primes in arithmetic progressions (part I)
    23. Euler introduction to Gauss quadratic reciprocity
    24. Trigonometry of a triangle–sinus & cosinus
    25. Wlodzimierz Holsztynski, knolog
    26. Tichonov product
    27. Factorization in semigroups
    28. Nowe knole
    29. Knole w języku polskim
    30. Metric spaces — introduction
    31. Topology — compact spaces II
    32. Topology–singular spaces
    33. the last summer concert in san jose
    34. California in poetry
    35. threeway
    36. san jose blues
    37. san francisco blues
    38. open your arcs
    39. Tom Wachtel, [I was running out of …]
    40. Tom Wachtel, [on the sand at…]
    41. “september”
    42. Topological sequences and convergence
    43. Topology–Arkhangelskii nets
    44. Topology–compact spaces I
    45. Topological product of two spaces. Hausdorff spaces.
    46. Trigonometry
    47. Total logarithmic series
    48. “affinity”
    49. [close your eyes…]
    50. “San Jose”
    51. willow girl
    52. heaven california
    53. “phase transitions”
    54. “california?”
    55. “dimensions”
    56. bachelor life
    57. “spring in california”
    58. [day -]
    59. Singular product of two spaces. Double limit.
    60. Art of Agreeing — painless tax
    61. The Birkhoff lattice of topologies
    62. Left topologies
    63. Topology — Kolmogorov axiom
    64. Topological subbases and bases
    65. Complexity of sorting
    66. ∞-Metrics
    67. Even perfect numbers and Mersenne primes
    68. Fermat sequence base b
    69. Harmonic series & Euler’s gamma
    70. 4-Baroque numbers with utmost 4 different prime divisors
    71. 3-Baroque numbers with utmost 3 different prime divisors
    72. Mathematical notation
    73. Baroque numbers – 2
    74. Number theory — ideals in Z, and the greatest common divisor
    75. Baroque numbers – 1
    76. Infinitude of primes – 2
    77. Number theory — Gothic numbers
    78. log and exp–a constructive and an axiomatic approaches
    79. Aleksandrov 2-point space
    80. Topology — short-short introduction
    81. Art of Agreeing — patent law
    82. Topology — the closure operation
    83. Integration of monotone functions
    84. The ground level properties of integral
    85. Metric spaces universal for 2-point spaces
    86. Products of bounded primes
    87. Sequences of pairwise coprime integers
    88. Mathematics — right triangles
    89. Art of Agreeing — United Nations
    90. Mathematics — two definitions
    91. Government wa(steful wa)ys
    92. Art of Agreeing — index
    93. Metric universality of (R^n d_m) — part 2
    94. Iso-graphs of metric maps into R (part 1)
    95. Metric universality of (R^n d_m) — part 1
    96. Metric spaces universal for 3- and 4-point spaces
    97. Number theory–units, composites, and primes
    98. Social life & energy saving
    99. Topological spaces and continuous mappings. Isolated points.
    100. Topological weight
    101. Mathematics — Euclid-Heron area of a triangle
    102. Connected spaces
    103. Art of Agreeing — marriage versus law & government
    104. Art of Agreeing — introduction
    105. Dabanese — index
    106. Linear orders in topological spaces
    107. Topological cuts and miscuts
    108. Closed sets. T1-spaces.
    109. Topology — the interior operation
    110. Mathematics — triangles
    111. Continuity of the piecewise continuous functions
    112. Topological subspaces
    113. Art of Agreement — medical insurance
    114. Art of Agreeing — business & stock market
    %d bloggers like this: