مبرهنة زيكندورف: تمثيل الأعداد الصحيحة بأرقام فيبوناتشي

مبرهنة زيكندورف

تعد مبرهنة زيكندورف (Zeckendorf's theorem)، التي سميت على اسم عالم الرياضيات الهاوي إدوارد زيكندورف، نتيجة رياضية هامة تتعلق بكيفية تمثيل الأعداد الصحيحة الموجبة كمجموع لأرقام فيبوناتشي. تنص المبرهنة على أن كل عدد صحيح موجب يمكن تمثيله بشكل فريد كمجموع لواحد أو أكثر من أرقام فيبوناتشي المتميزة، بشرط ألا يتضمن المجموع أي رقمين متتاليين من سلسلة فيبوناتشي.

كيفية عمل تمثيل زيكندورف

بشكل أكثر دقة، إذا كان N أي عدد صحيح موجب، فإنه توجد أعداد صحيحة موجبة $c_i \ge 2$ بحيث تكون $c_{i+1} > c_i + 1$، مما يضمن عدم وجود رقمين متتاليين في السلسلة. يسمى هذا المجموع تمثيل زيكندورف للعدد N، ويمكن من خلاله اشتقاق ما يعرف بـ ترميز فيبوناتشي.

مثال توضيحي

لنأخذ العدد 64 كمثال. يمكن تمثيله بعدة طرق كمجموع لأرقام فيبوناتشي، ولكن هناك طريقة واحدة فقط تحقق شروط مبرهنة زيكندورف (عدم التتالي):

• تمثيل زيكندورف: 64 = 55 + 8 + 1 (أرقام فيبوناتشي غير متتالية).
• تمثيلات أخرى (غير صحيحة وفق زيكندورف): 64 = 34 + 21 + 8 + 1 (هنا 34 و 21 متتاليان في السلسلة، لذا لا يعتبر تمثيل زيكندورف).

لإيجاد تمثيل زيكندورف لأي عدد، يتم استخدام الخوارزمية الجشعة (Greedy Algorithm)، والتي تعتمد على اختيار أكبر رقم فيبوناتشي ممكن في كل مرحلة. على سبيل المثال:

• العدد 11 = 8 + 3.
• العدد 13 = 13 (لأنه رقم فيبوناتشي بحد ذاته).
• العدد 31 = 21 + 8 + 2.

إثبات المبرهنة

تتكون مبرهنة زيكندورف من جزأين أساسيين: الوجود و التفرد.

1. إثبات الوجود

يمكن إثبات وجود التمثيل عن طريق الاستقراء الرياضي. في الحالة الأساسية، العدد 1 له تمثيل زيكندورف وهو $n=1=F_2$.

بافتراض أن جميع الأعداد $k < n$ لها تمثيل زيكندورف، لنفترض وجود $j$ بحيث يكون $F_j < n < F_{j+1}$. عندها يكون $n - F_j < n$، وبالتالي يوجد تمثيل زيكندورف للفرق $n - F_j$.

2. إثبات التفرد

لإثبات أن هذا التمثيل فريد، يمكن استخدام المتطابقة الرياضية التي تنص على أن مجموع أرقام فيبوناتشي غير المتتالية التي تنتهي عند $F_n$ يكون دائماً أقل من $F_{n+1}$.

يمكن إثبات هذه المتطابقة بالاستقراء أو من خلال حجج العد. في حال وجود تمثيلين مختلفين لنفس العدد، سيؤدي ذلك إلى تناقض رياضي، مما يثبت أن كل عدد صحيح موجب له تمثيل زيكندورف واحد فقط.