Θεώρημα Zeckendorf

[AlexandrosG]

Να αποδείξετε ότι κάθε φυσικός γράφεται με μοναδικό τρόπο ώς άθροισμα διαφορετικών μη διαδοχικών αριθμών Fibonacci.

[dement]

Για να δουμε. Αποδεικνυουμε τη μοναδικοτητα.

Εστω ο ελαχιστος φυσικος που μπορει να γραφει ως δυο διαφορετικα αθροισματα μη διαδοχικων ορων Fibonacci. Εστω ο ελαχιστος ορος του πρωτου και ο ελαχιστος ορος του δευτερου αθροισματος, και εστω . Τοτε, με τον αναδρομικο τυπο, μπορουμε να γραψουμε τον ως , οπου το ειναι η η αθροισμα μη διαδοχικων ορων Fibonacci που περιλαμβανει ακριβως εναν απο τους . Ετσι, εχουμε τροπο να γραψουμε και τον ως δυο διαφορετικα αθροισματα αντιβαινοντας στην υποθεση του ελαχιστου, οποτε εχουμε ατοπο.

Τωρα αποδεικνυουμε το 'καθε'.

Ο αριθμος (οπου ορος της ακολουθιας Fibonacci ) ειναι ο αριθμος των τροπων με τους οποιους μπορουμε να επιλεξουμε αντικειμενα απο κουτια, το πολυ ενα ανα κουτι, χωρις να χρησιμοποιησουμε διαδοχικα κουτια. Αυτο αποδεικνυεται ευκολα με επαγωγη και την ιδιοτητα Fibonacci.

Ετσι, με τους αριθμους Fibonacci μικροτερους η ισους του μπορουμε να φτιαξουμε αθροισματα χωρις να χρησιμοποιησουμε διαδοχικους ορους.

Επισης, ολα αυτα τα αθροισματα θα ειναι μικροτερα του που αποδεικνυεται επισης με επαγωγη (αν το αθροισμα δεν περιεχει τον θα ειναι μικροτερο του , ενω αν τον περιεχει δε θα περιεχει τον και θα ειναι ετσι μικροτερο του ).

Ετσι, τα αθροισματα που μπορουμε να φτιαξουμε θα ειναι ακριβως οι φυσικοι αριθμοι μικροτεροι του (λογω μοναδικοτητας).

Δημητρης Σκουτερης