قضيه نمايش فيبوناتچي

اعداد زير را درنظر بگيريد :…,1,1,2,3,5,8,13,21,34 با كمي دقت متوجه مي شويم كه ازعدد سوم به بعد هر عدد از مجموع دو عدد قبلي به دست مي آيد .اين اعداد را اعداد فيبوناتچي گويند وآن ها را با نمايش مي دهند كه در آن و براي .
با كمي دقت در مي يابيم كه براي و اين اعداد بي كران هستند.
از قضيه ي بنيادي حساب مي دانيم كه هر عدد طبيعي 1<n داراي نمايشي يكتا به صورت است كه در آن ها اعداد اول متمايز و ها اعداد طبيعي و . در اين مقاله مي خواهيم نشان دهيم هر عدد طبيعي نيز داراي نمايشي يكتا به شكل مجموع اعداد فيبوناتچي است .

قضيه : هر عدد طبيعي N را مي توان به صورت حاصل جمع اعداد فيبوناتچي متمايز نوشت :

به طوري كه : الف : براي هر 1- r و … و 1= i ، .
ب : .

توضيح: اين نمايش را نمايش متعارف N گويند .

اثبات :ابتدا حكم زير را با كمك استقرا ثابت مي كنيم : براي هر عدد طبيعي ، تمامي اعداد طبيعي نابيش تر از داراي نمايش متعارف هستند .براي2,3=n حكم واضح است .اگر حكم براي تمامي اعداد طبيعي نابيش تر از برقرار و باشد ، چون پس و لذا . با استفاده ازفرض استقرا :كه و پس و [چرا ؟] .
از اين بحث نتيجه مي گيريم كه هر عدد طبيعي نابيش تر از داراي نمايش متعارف است . حال اگر N عدد طبيعي دلخواهي باشد ، به دليل بي كران بودن اعداد فيبوناتچي ، عدد طبيعي m موجودست كه پس با استفاده از موضوعي كه در بالا ثابت شد N داراي نمايش متعارف است .

قضيه : نمايش متعارف N يكتاست .
اثبات : ابتدا حكم زير را با كمك استقرا ثابت مي كنيم : براي هر عدد طبيعي ، نمايش متعارف تمامي اعداد طبيعي نابيش تر از يكتا است .براي2,3=n حكم واضح است . اگر حكم براي تمامي اعداد طبيعي نابيش تر از برقرار و باشد . ادعا مي كنيم كه در نمايش متعارف N، جمله ي حتماً ظاهر مي شود . چرا كه در غير اين صورت خواهيم داشت :
اگر n زوج و مثلاً 2k باشد ، بزرگ ترين مجموعي كه مي تواند كانديداي نمايش متعارف N باشد به صورت زير است :

اگر n فرد و مثلاً 1+2k باشد ، بزرگ ترين مجموعي كه مي تواند كانديداي نمايش متعارف N باشد به صورت زير است :

اين بحث نشان مي دهد كه در نمايش متعارف N ، جمله ي حتماً بايد ظاهر شود . حال اگر N دو نمايش متعارف به صورت داشته باشد آن گاه و لذا چون پس طبق فرض استقرا نمايش متعارف يكتاست و لذا r=t و انديس هاي متناظر مساوي هستند و اين يعني نمايش متعارف N يكتاست . بنابراين هر عدد طبيعي نابيش تراز داراي نمايش متعارف يكتاست . . حال اگر N عدد طبيعي دلخواهي باشد ،چون اعداد فيبوناتچي بي كران هستند ، پس عدد طبيعي m موجودست كه . بنابراين طبق موضوع فوق ، N داراي نمايش متعارف يكتاست .