Zeckendorfs teorem

De första 89 naturliga talen i Zeckendorf-form. Varje rektangel har ett Fibonacci-tal

F j

som bredd (blått tal i mitten) och

F j -1

som höjd. De vertikala banden har bredd 10.

Inom matematik är Zeckendorfs sats , uppkallad efter den belgiske amatörmatematikern Edouard Zeckendorf , en sats om representationen av heltal som summor av Fibonacci - tal .

Zeckendorfs teorem säger att varje positivt heltal kan representeras unikt som summan av ett eller flera distinkta Fibonacci-tal på ett sådant sätt att summan inte inkluderar två på varandra följande Fibonacci-tal. Mer exakt, om $N$ är något positivt heltal, finns det positiva heltal $c i \geq 2$ , med $c i + 1 > c i + 1$ , så att

N=\sum _{i=0}^{k}F_{c_{i}},

där $F n$ är det $n$ ^:te Fibonacci-talet. En sådan summa kallas Zeckendorf-representationen av $N$ . Fibonacci-kodningen av N $kan$ härledas från dess Zeckendorf-representation.

Till exempel är Zeckendorf-representationen av 64

64 = 55 + 8 + 1

.

Det finns andra sätt att representera 64 som summan av Fibonacci-tal

64 = 55 + 5 + 3 + 1

64 = 34 + 21 + 8 + 1

64 = 34 + 21 + 5 + 3 + 1

64 = 34 + 13 + 8 + 5 + 3 + 1

men dessa är inte Zeckendorf-representationer eftersom 34 och 21 är på varandra följande Fibonacci-tal, liksom 5 och 3.

För varje givet positivt heltal, kan dess Zeckendorf-representation hittas genom att använda en girig algoritm , genom att välja största möjliga Fibonacci-tal i varje steg.

Historia

Medan satsen är uppkallad efter författaren med samma namn som publicerade sin artikel 1972, hade samma resultat publicerats 20 år tidigare av Gerrit Lekkerkerker . Som sådan är satsen ett exempel på Stiglers lag om eponymi .

Bevis

Zeckendorfs teorem har två delar:

Existens : varje positivt heltal $n$ har en Zeckendorf-representation.
Unikhet : inget positivt heltal $n$ har två olika Zeckendorf-representationer.

Den första delen av Zeckendorfs teorem (existens) kan bevisas genom induktion . För $n = 1, 2, 3$ är det helt klart sant (eftersom dessa är Fibonacci-tal), för $n = 4$ har vi $4 = 3 + 1$ . Om $n$ är ett Fibonacci-tal är vi klara. Annars finns det $j$ så att $F j < n < F j + 1$ . Antag nu att varje positivt heltal $a < n$ har en Zeckendorf-representation (induktionshypotes) och betrakta $a = n - F j$ . Eftersom $a < n$ , har $a$ en Zeckendorf-representation genom induktionshypotesen. Samtidigt är $a = n - F j < F j + 1 - F j = F j - 1$ (vi tillämpar definitionen av Fibonacci-tal i den sista likheten), så Zeckendorf-representationen av $a$ innehåller inte $F j - 1$ , och innehåller därför inte heller $F j$ . Som ett resultat $n$ representeras som summan av $F j$ och Zeckendorf-representationen av $a$ , så att Fibonacci-talen som ingår i summan är distinkta.

Den andra delen av Zeckendorfs teorem (unikhet) kräver följande lemma:

Lemma : Summan av en icke-tom uppsättning distinkta, icke-konsekutiva Fibonacci-tal vars största medlem är

F j

är strikt mindre än nästa större Fibonacci-tal

F j + 1

.

Lemmat kan bevisas genom induktion på $j$ .

Ta nu två icke-tomma uppsättningar $S$ och $T$ av distinkta icke-konsekutiva Fibonacci-tal som har samma summa, ${\textstyle \summa _ {x\in S}x=\summa _{x\in T}x}$ . Betrakta uppsättningarna $S'$ och $T'$ som är lika med $S$ och $T$ från vilka de gemensamma elementen har tagits bort (dvs. $S'=S\setminus T$ och $T'=T\setminus S$ ). Eftersom $S$ och $T$ hade samma summa, och vi har tagit bort exakt elementen från $S\cap T$ från båda mängderna, $S'$ och $T'$ måste också ha samma summa, ${\textstyle \sum _{x\in S'}x=\summa _{x\ i T'}x}$ .

Nu kommer vi att visa motsägelsefullt att åtminstone en av $S'$ och $T'$ är tom. Antag motsatsen, dvs. e. att $S'$ och $T'$ båda är icke-tomma och låter den största medlemmen av $S'$ vara $F s$ och den största medlemmen av $T'$ vara $F t$ . Eftersom $S'$ och $T'$ inte innehåller några gemensamma element, $F s \neq F t$ . Utan förlust av generalitet , anta att $F s < F t$ . Sedan genom lemma, ${\textstil \sum _{x\in S'}x<F_{s+1}} ,$ och, genom att ${\textstyle F_{s}<F_{s+1}\leq F_{t}}$ , ${\textstyle \sum _{x\in S'}x <F_{t}}$ , medan tydligt ${\textstyle \sum _{x\in T'}x\geq F_{t}}$ . Detta motsäger det faktum att $S'$ och $T'$ har samma summa, och vi kan dra slutsatsen att antingen $S'$ eller $T'$ måste vara tom.

Antag nu (igen utan förlust av allmänhet) att $S'$ är tom. Då $S'$ summan 0, och så måste $T'$ . Men eftersom $T'$ bara kan innehålla positiva heltal måste den också vara tom. Sammanfattningsvis: $S'=T'=\emptyset$ vilket innebär $S=T$ , vilket bevisar att varje Zeckendorf-representation är unik.

Fibonacci multiplikation

Man kan definiera följande operation $a\circ b$ på naturliga tal $a$ , $b$ : givet Zeckendorf-representationerna ${\displaystyle a=\summa _{i=0}^{k}F_{c_{i}}\;(c_{i}\geq 2)} och b = ∑$ j $= \sum _{j=0}^{l}F_{d_{j}}\;(d_{j}\geq 2)} vi$ definierar Fibonacci-produkten $a\circ b=\sum _{i=0}^{k}\sum _{j=0}^{l}F_{c_{i}+d_{j}}.$

Till exempel är Zeckendorf-representationen av 2 $F_{3}$ och Zeckendorf-representationen av 4 är $F_{4}+F_{2}$ ( ${\ displaystyle F_{1}}$ är inte tillåten från representationer), så $2\circ 4=F_{3+4}+F_{ 3+2}=13+5=18.$

(Produkten är inte alltid i Zeckendorf-form. Till exempel, $4\circ 4=(F_{4}+F_{2})\circ (F_{4}+F_{2$ =

En enkel omarrangering av summor visar att detta är en kommutativ operation; dock Donald Knuth det överraskande faktum att denna operation också är associativ .

Representation med negafibonacci-tal

Fibonacci-sekvensen kan utökas till negativt index $n$ med hjälp av den omarrangerade återfallsrelationen

F_{n-2}=F_{n}-F_{n-1},

vilket ger sekvensen av " negafibonacci "-nummer som uppfyller

F_{-n}=(-1)^{n+1}F_{n}.

Vilket heltal som helst kan representeras unikt som en summa av negafibonacci-tal där inga två på varandra följande negafibonacci-tal används. 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 den tomma summan .

$0 = F -1 + F -2$ , till exempel, så att representationens unikhet beror på villkoret att inga två på varandra följande negafibonacci-tal används.

Detta ger ett system av kodande heltal , liknande representationen av Zeckendorfs teorem. I strängen som representerar heltal $x$ , är den $n :$ ^te siffran 1 om $F -n$ förekommer i summan som representerar $x$ ; den siffran är 0 annars. Till exempel kan 24 representeras av strängen 100101001, som har siffran 1 på platserna 9, 6, 4 och 1, eftersom 24 $= F -1 + F -4 + F -6 + F -9$ . Heltalet $x$ representeras av en sträng med udda längd om och endast om $x > 0$ .

Se även

Zeckendorf, E. (1972). "Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas". Tjur. Soc. R. Sci. Liège (på franska). 41 : 179–182. ISSN 0037-9565 . Zbl 0252.10011 .

externa länkar

Weisstein, Eric W. "Zeckendorfs sats" . MathWorld .
Weisstein, Eric W. "Zeckendorf-representation" . MathWorld .
Zeckendorfs teorem vid cut-the-knoten
GM Phillips (2001) [1994], "Zeckendorf representation" , Encyclopedia of Mathematics , EMS Press
OEIS -sekvens A101330 (Knuths Fibonacci (eller cirkel) produkt)

Den här artikeln innehåller material från bevis på att Zeckendorf-representationen av ett positivt heltal är unik på PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .