Negafibonacci

I matematik är icke -Gafibonacci-tal de negativt indexerade elementen i Fibonacci-sekvensen .

Negafibonacci-talen definieras induktivt av följande rekursiva relation:

F − 1 = 1,
F -2 = -1,
Fn = F ( n +2) -F (n+1) .

De kan också definieras med formeln F −n = (−1) n+1 F n .

De första 10 numren i nega-Fibonacci-sekvensen är:

n	F( n )
−1	ett
−2	−1
−3	2
−4	−3
−5	5
−6	−8
−7	13
−8	−21
−9	34
−10	−55

Heltalsrepresentation

Vilket heltal som helst kan representeras unikt – enligt Donald Knuths arbete [1] – som summan av icke-Fibonacci-tal som inte använder två på varandra följande icke-Fibonacci-tal. Till exempel:

−11 = F −4 + F −6 = (-3) + (-8)
12 = F - 2 + F- 7 = (-1) + 13
24 = F − 1 + F− 4 + F− 6 + F −9 = 1 + (-3) + (-8) + 34
−43 = F −2 + F −7 + F −10 = (-1) + 13 + (-55)
0 representeras av en tom summa.

Det är anmärkningsvärt att 0 = F −1 + F −2 , till exempel, så att representationens unikhet verkligen beror på villkoret att inte använda två på varandra följande icke-Fibonacci-tal.

Detta gör att nega-Fibonacci-kodningssystemet kan koda heltal som liknar representationen av Zeckendorfs teorem för omkodning av tal med binär representation. I sekvensen som representerar heltal x , n th , är siffran 1 om F n förekommer i summan som representerar x ; den siffran är inte 0. Till exempel kan siffran 24 representeras av sekvensen 100101001, som har siffran 1 på platserna 9, 6, 4 och 1 eftersom 24 = F −1 + F −4 + F − 6 + F - 9 . Ett heltal x representeras av en sekvens med udda längd om och endast om . $x>0$

Identiteter

Relationer till den normala positiva sekvensen av Fibonacci-tal:

$F(-n)=(-1)^{n+1}\cdot F(n)$

Anteckningar

↑ "Neg Fibonacci Numbers and the Hyperbolic Plane" (Papper presenterat vid årsmötet för Mathematical Association of America, Fairmont Hotel, San Jose , Kalifornien, 2008-12-11) [1]