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

اعداد زیر را درنظر بگیرید :…,۱,۱,۲,۳,۵,۸,۱۳,۲۱,۳۴ با کمی دقت متوجه می شویم که ازعدد سوم به بعد هر عدد از مجموع دو عدد قبلی به دست می آید .این اعداد را اعداد فیبوناتچی گویند وآن ها را با نمایش می دهند که در آن و برای .
با کمی دقت در می یابیم که برای و این اعداد بی کران هستند.
از قضیه ی بنیادی حساب می دانیم که هر عدد طبیعی ۱<n دارای نمایشی یکتا به صورت است که در آن ها اعداد اول متمایز و ها اعداد طبیعی و . در این مقاله می خواهیم نشان دهیم هر عدد طبیعی نیز دارای نمایشی یکتا به شکل مجموع اعداد فیبوناتچی است .

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

به طوری که : الف : برای هر ۱- r و … و ۱= i ، .
ب : .

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

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

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

اگر n فرد و مثلاً ۱+۲k باشد ، بزرگ ترین مجموعی که می تواند کاندیدای نمایش متعارف N باشد به صورت زیر است :

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