Don't take life too seriously: it's just a temporary situation

Fibonacci generalizzati (numeri di)

Sequenze  Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Proprietà
  3. 3. Formule
  4. 4. Serie

Sono così chiamati i numeri appartenenti a sequenze ottenute dalla ricorrenza Gn = Gn – 1 + Gn – 2, uguale a quella di Fibonacci, ma con differenti valori iniziali.

Appartengono a questa categoria i numeri di Fibonacci, i numeri di Fibonacci gaussiani e i numeri di Lucas.

 

La formula per Gn, analoga a quella di Binet, è Formula per i numeri di Fibonacci generalizzati.

Altre formule equivalenti sono:

Gn = G1Fn + G0Fn – 1 = F0Gn – 1 + F1Gn;

Formula per i numeri di Fibonacci generalizzati;

Formula per i numeri di Fibonacci generalizzati.

Dalla prima formula si ottiene Formula per i numeri di Fibonacci.

 

Il valore Formula per la definizione di μ è detto “caratteristica” della sequenza Gn; per la sequenza di Fibonacci μ = 1 e per quella di Lucas μ = –5.

 

Come per i numeri di Fibonacci, la definizione può essere estesa a indici negativi, ripercorrendo all’indietro la definizione, ottenendo Gn = (–1)nG0Fn + 1 + (–1)n + 1G1Fn (Koshy, 1998).

 

La definizione può anche essere estesa a indici reali, definendo Formula per i numeri di Fibonacci generalizzati con indici reali (vedi funzione Fx), definizione che preserva la proprietà Gx = Gx – 1 + Gx – 2.

 

Si possono anche considerare ricorrenze ancora più generali: se Un = pUn – 1 + qUn – 2, la formula per Un, analoga a quella di Binet è Formula per i numeri di Fibonacci generalizzati.

Anche questa definizione può essere estesa a numeri reali, definendo Formula per i numeri di Fibonacci generalizzati con indici reali (vedi funzione Fx), per p2 ≠ –4q, ottenendo una funzione che coincide con la definizione consueta per x intero e preservando la proprietà Ux = pUx – 1 + qUx – 2.

 

Date le successioni definite dalle ricorrenze U0 = 0, U1 = 1, Un = xUn – 1 + Un – 2, V0 = 2, V1 = x, Vn = xVn – 1 + Vn – 2, Thomas J. Osler dimostrò che:

Formula che coinvolge numeri di Fibonacci generalizzati, per n pari, e in particolare Formula che coinvolge numeri di Fibonacci e di Lucas, per n pari;

Formula che coinvolge numeri di Fibonacci generalizzati, per n dispari, e in particolare Formula che coinvolge numeri di Fibonacci e di Lucas, per n dispari.

Se U0 = 0 e U1 = 1, la successione può anche essere ottenuta come Un = En – 1(p, –q); dove En(x, α) è un polinomio di Dickson di seconda specie.

La successione associata, definita come V0 = 0, V1 = p e Vn = pVn – 1 + qVn – 2, può anche essere ottenuta come Vn = Dn(p, –q); dove Dn(x, α) è un polinomio di Dickson di prima specie.

 

Una diversa generalizzazione si ottiene definendo Gn = Gn – 1 + Gn – 2 + k; in questo caso:

  • con G0 = 0 e G1 = 1 otteniamo Gn = Fn + k(Fn + 1 – 1) e Limite per n tendente a infinito di G(n) / F(n) (Shallit, 1976);

  • con G0 = 2 e G1 = 1 otteniamo Gn = Ln + kFn – 1Limite per n tendente a infinito di G(n) / L(n) (Koshy, 1999).

 

Tra le innumerevoli varianti, segnalo la sequenza che inizia con a0 = 4, a1 = 0, a2 = 0, a3 = 3, an + 4 = an + 1 + an; i primi termini sono quindi: 4, 0, 0, 3, 4, 0, 3, 7, 4, 3, 10, 11, 7, 13, 21, 18, 20, 34, 39, 38, 54, 73, 77, 92, 127, 150, 169, 219, 277, 319, 388, 496, 596, 707, 884.

La curiosa proprietà di questa sequenza, dimostrata da Mihàly Bencze nel 1998, è che an è divisibile per n se n è primo. Sfortunatamente an è divisibile per n anche per vari valori composti di n, altrimenti avremmo uno splendido test per stabilire se un numero è primo. I casi del genere con n inferiore a 1000 sono: 4, 10, 25, 34, 38, 46, 62, 94, 106, 122, 158, 166, 214, 218, 226, 235, 274, 278, 302, 334, 338, 346, 362, 394, 395, 398, 415, 422, 454, 458, 466, 482, 514, 515, 526, 542, 586, 634, 662, 694, 698, 706, 758, 766, 785, 818, 842, 878, 886, 905, 934, 998.

 

Anche la sequenza di Ondrej Such, definita dalla ricorrenza a0 = 3, a1 =0, a2 = 2, an = an – 2 + an – 3, ha la stessa proprietà; i primi valori sono: 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853.

Anche in questo caso ogni n primo divide an ed esistono numeri composti n che dividono an, però sono molto rari; i primi sei sono: 271441 = 5212, 904631 = 7 • 13 • 9941, 16532714 = 2 • 112 • 53 • 1289, 24658561 = 19 • 271 • 4789, 27422714 = 2 • 112 • 47 • 2411 e 27664033 = 3037 • 9109 (Stanislav Jakubec, Karol Nemoga, 1986).

Questa sequenza pone un interessante problema, tuttora aperto: è stato dimostrato che ana2n mod 2 e ana3n mod 3, ma non è noto se questa proprietà valga sostituendo a 2 o 3 un qualsiasi altro numero primo.

 

Alla luce di questi risultati è piuttosto sorprendente che esista una sequenza di polinomi che genera polinomi primi (ossia irriducibili) per tutti e soli gli indici primi, eppure i polinomi di Fibonacci Fn(x) hanno la proprietà che Fn(x) è irriducibile se e solo se n è primo.

Se U0 = 0 e U1 = 1 la successione può anche essere ottenuta come Un = En – 1(p, –q); dove En(x, α) è un polinomio di Dickson di seconda specie.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.