دنباله فیبوناچی

توالی فیبوناچی یک توالی عدد صحیح است که توسط یک رابطه عود خطی ساده تعریف شده است. این دنباله در بسیاری از تنظیمات در ریاضیات و علوم دیگر ظاهر می شود. به طور خاص ، شکل بسیاری از ارگانیسم های بیولوژیکی که به طور طبیعی رخ می دهد توسط توالی فیبوناچی و نسب نزدیک آن ، نسبت طلایی اداره می شود.

اعداد فیبوناچی به عنوان تعداد مارپیچ در برگ ها و سرهای بذر نیز ظاهر می شوند.

اعداد فیبوناچی شرایط دنباله اعداد صحیح است که در آن هر اصطلاح مجموع دو اصطلاح قبلی است

[ شروع و f_1 = f_2 = 1 ، & f_n = f_ + f _. end ]

چند اصطلاح اول است

[1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ، ldots. ]

فهرست

• بیان شکل بسته
• کسر
• مشکلات ذکر شده
• هویت های مربوط به سری فیبوناچی
• تابع
• خواص قابل تقسیم
• قضیه Zeckendorf

بیان شکل بسته

این فرمول (که اغلب فرمول بینه نامیده می شود) از نتیجه کلی برای روابط عود خطی ناشی می شود ، اما می توان آن را مستقیماً با القاء اثبات کرد. بگذارید (g_n = frac<phi^n-<overline phi>^n> <sqrt <5>>)هدف این است که ثابت کنیم (f_n = g_n ) با القاء در (n ). موارد پایه (g_1 = g_2 = 1 ) است که مشخص است. اکنون فرض کنید (g_k = f_k ) برای همه (k

[ شروع f_n & = f_+f_ \ & = g_+g_ & text<(inductive hypothesis)>\ &= frac1> بزرگ ( phi^-<overline<phi>>^Big)+frac1> بزرگ ( phi^-<overline<phi>>^Big) \ &= frac1> بزرگ ( phi^+ phi^-<overlinephi>^-<overlinephi>^Big) \ &= frac1> بزرگ ( phi^n-<overlinephi>^n big) = g_n ، end ]

جایی که خط آخر از این واقعیت ناشی می شود که ( phi ) و ( overline phi ) دو ریشه معادله (x^2 = x+1 ) هستند.(_مربع)

توجه داشته باشید که برای (n ge 1 ) ، اصطلاح ( frac<<overlinephi>^n>>) کوچک است ، مطمئناً بین (-0. 3 ) و (0. 3 ). بنابراین (f_n ) نزدیکترین عدد صحیح به ( frac<phi^n>> ).

بنابراین نسبت اعداد فیبوناچی پی در پی باید تقریباً باشد

این را می توان به راحتی با استفاده از فرمول Binet ثابت کرد.

کسر

دنباله فیبوناچی به عنوان شمارنده ها و مخرج همگرایی ها به کسری ساده ادامه می یابد

این کسر مداوم برابر است با ( phi ، ) زیرا آن را برآورده می کند (x = 1+ frac1 ) (و بیشتر از 1 است).

The ( n^ ext) convergent to this continued fraction is ( frac>) ، بنابراین این اثبات دیگری می دهد که ( lim limits_frac>= phi ).

مشکلات ذکر شده

مانند اعداد کاتالان ، اعداد فیبوناچی انواع مختلفی از اشیاء ترکیبی را به حساب می آورند. در اینجا چهار مثال آورده شده است.

(1) (f_n ) تعداد ترکیبات (n-1 ) متشکل از (1 ) s و (2 ) s است.(ترکیبی از (n-1 ) عبارتی از (n-1 ) به عنوان تعداد قطعات است ، که در آن ترتیب قطعات مهم است.)

[ شروع 5 & = 1+1+1+1+1 \ & = 1+1+1+2 \ & = 1+1+2+1 \ & = 1+2+1+1 \ & = 2+1+1+1 \ & = 1+2+2 \ & = 2+1+2 \ & = 2+2+1 ، end ]

بنابراین (f_6 = 8. )

.

.

(4) (f_n ) تعداد زیر مجموعه های (<1,2,ldots,n-2>) که حاوی هیچ جفت شماره متوالی نیست.

برای دیدن اینکه اعداد فیبوناچی این اشیاء را به حساب می آورند ، اجازه دهید تعداد اشیاء برابر (g_n ) برابر شوند و نشان دهند که (g_n = g_+g_ ). سپس تأیید کنید که (f_1 = g_1 ) و (f_2 = g_2 ) ، و اثبات کامل است.

به عنوان مثال ، برای اثبات (4) ، با (g_1 = 1 ، g_2 = 1 ، g_3 = 2 ، g_4 = 3 ) شروع کنید ، و سپس فرض کنید (s ) زیر مجموعه ای از ( است.<1,2,ldots,n-2>) بدون هیچ شماره متوالی در آن. چنین مجموعه هایی وجود دارد که (s ) وجود دارد که حاوی (n-2 ) نیستند. اگر (s ) حاوی (n-2 ) باشد ، پس از آن حاوی (n-3 ) نیست ، بنابراین (s ) با گرفتن زیر مجموعه ای از () بدست می آید.<1,2,ldots,n-4>) و پرتاب در (n-2 ). بنابراین (g_ ) چنین مجموعه هایی وجود دارد (s ). این ثابت می کند که (g_n = g_+g _ ، ) طبق دلخواه.

پاسخ خود را ارسال کنید

ترکیبی از (n ) عبارتی از (n ) به عنوان مجموع از اعداد صحیح مثبت نیست ، جایی که سفارش اهمیت دارد. توجه داشته باشید که (n = n ) به عنوان ترکیبی از (n ) حساب می شود.

بگذارید (c_n ) تعداد ترکیبات (n ) باشد که هیچ بخشی از آن برابر با 1 باشد.

به عنوان مثال ، (c_6 = 5 ) زیرا (6 = 6 = 4+2 = 3+3 = 2+4 = 2+2+2. )

پاسخ خود را ارسال کنید

یک دلقک می تواند با یک مرحله یا دو مرحله از یک پله عبور کند. به عنوان مثال ، او می تواند از کف به مرحله اول و سپس به سوم صعود کند ، یا می تواند از کف به مرحله اول ، سپس به دوم و سپس در نهایت به سوم صعود کند.

اگر یک راه پله 10 قدم داشته باشد ، از چند طریق دلقک می تواند از آن صعود کند؟

شفاف سازی:

• وقتی او از صعود می کند (<9>^ متن ) قدم به (<10>^ متن ، ) او از کل پله صعود کرده است. یعنی مرحله آخر طبقه دوم است.
• نظمی که او از راه پله بالا می رود مهم است!

جایزه: آن را تعمیم دهید.

پاسخ خود را ارسال کنید

اعداد فیبوناچی توسط

• (f (0) = 0 )
• (f (1) = 1 )
• (f (n) = f (n-1) + f (n-2). )

بنابراین ، چند مورد اول (0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13. )

اگر این را به اعداد منفی تعمیم دهیم ، (f (-8)؟ ) چیست

هویت های مربوط به سری فیبوناچی

تعداد کمی از هویت وجود دارد که در رابطه با شماره های مختلف فیبوناچی وجود دارد. برای مثال،

که نتیجه مفیدی را دارد که تعداد فیبوناچی متوالی به نظر می رسد.

همانطور که معمولی است ، بیشترین اثبات این هویت از طریق القاء است. برای (n = 2،3 ) واضح است ، و اکنون فرض کنید که برای (n ) صادق است. سپس

[ شروع f_^2-f_nf_ & = f_^2-f_n (f_n+f _) \ & = f_ (f_-f_n)-f_n^2 \ & = f_f_-f_n^2 \ & =-((-1)^ = (-1)^ ، پایان ]

بنابراین برای (n+1 ) صادق است.(_مربع)

اثبات بقیه این هویت ها مشابه است.

• (1a) (f_ = f_^2+f_n^2 )
• (1b) (f_ = f_n (f_+f_) )

پاسخ خود را ارسال کنید

روزی خرگوش و یک لاک پشت در یک مسابقه رقابت می کردند.

خرگوش سریع می تواند در فاصله فزاینده ای شبیه به دنباله فیبوناچی (از بین بردن 1 ترمی اول) همانطور که در بالا نشان داده شده است: (1 ، 2 ، 3 ، 5 ، 8 ، 13 ، ldots. )

لاک پشت آهسته می تواند در فاصله فزاینده ای از یک دنباله حسابی از 1 فاصله همانطور که نشان داده شده است بچرخد: (1 ، 2 ، 3 ، 4 ، 5 ، ldots )

گرچه به ظاهر حتی در سه مرحله اول ، خیلی زود پس از آن ، خرگوش به سرعت از حریف خود جلوتر رفت. با این حال ، در یک لحظه ، خرگوش ، با اطمینان از پیروزی خود ، برای چرت زدن متوقف شد. بعداً ، لاک پشت مسیر خود را با همان الگوی ادامه داد و در همان فاصله با خرگوش ملاقات کرد. سپس لاک پشت قبل از پیروزی در مسابقه تلاش خود را انجام داد.

با توجه به این داستان ، کمترین فاصله ممکن از شروع تا نقطه خواب خرگوش چقدر است؟

پاسخ خود را ارسال کنید

من اخیراً اتاق زیر شیروانی خود را تمیز می کردم و مجموعه ای از حداقل 14 چوب را پیدا کردم که یک آقا کنجکاو ایتالیایی چند سال پیش مرا فروخت. سعی کردم بفهمم چرا آن را از او خریداری کردم ، فهمیدم که این مجموعه دارای خاصیت باورنکردنی است که هیچ چوب (3 ) وجود ندارد که می تواند مثلث ایجاد کند. اگر این مجموعه دارای دو چوب طول (1 ) باشد که کوچکترین آنها هستند ، کمترین طول ممکن از ()<14>^ متن ) چوب؟

پاسخ خود را ارسال کنید

بگذارید ((x ، y) ) راه حل های عدد صحیح غیر منفی به نمودار هایپربولیک در بالا باشد.

اگر (x+y = n ) برای برخی از مربع های کامل (n ) ، جمع همه ممکن است (n؟ )

نکته: تنها اعداد فیبوناچی که مربع های کامل هستند 0 ، 1 و 144 هستند.

تابع

عملکرد تولید اعداد فیبوناچی است

این از گسترش است:

[ شروع big (1-x-x^2 big) big (f_1x + f_2x^2 + f_3x^3 + cdots big) & = f_1x + (f_2-f_1) x^2 + (f_3-f_2 + (f_3-f_2-f_1) x^3+(f_4-f_3-f_2) x^4+ cdots \ & = x+0x^2+ sum _^ infty (f_k-f_-f_) x^k \ & = x. _ square پایان ]

پاسخ خود را ارسال کنید

جمع بخش های فوق را پیدا کنید ، جایی که مخرج ها از پیشرفت هندسی پیروی می کنند و شمارنده ها دنباله فیبوناچی را دنبال می کنند.

پاسخ خود را ارسال کنید

بگذارید (f_n ) شماره فیبوناچی (n^ text ) را نشان دهد ، جایی که (f_0 = 0 ) ، (f_1 = 1 ) و (f_n = f_ + f_ ) برای (n = n =2،3،4 ،. )

مقدار (k ) را که معادله فوق را برآورده می کند ، پیدا کنید.

پاسخ خود را ارسال کنید

[ شروع 0. && 00000 Quad 00001 Quad 00001 Quad 00002 Quad 00003 Quad 00005 Quad 00008 \ && 00013 Quad 00021 Quad 00034 Quad Quad 00055 00055 00055 00055 00055 00055 00055 00055 0005555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555 پایان ]

موارد فوق چند رقم اول (در واقع 65) از بازنمایی اعشاری از کسری ( large frac1. ) را نشان می دهد اگر رقم ها را به پارتیشن های 5 تقسیم کنیم ، می بینیم که اعداد یک توالی فیبوناچی را تشکیل می دهند: (((()0،1،2،3،5،8،13 ، ldots ). چند عدد فیبوناچی مثبت را می توانیم قبل از شروع الگوی پیدا کنیم؟

توجه: به عنوان مثال ، فرض کنید که کسری برابر است [0. 00000 Quad 00001 Quad 00001 Quad 00002 Quad 00003 Quad 00009 ldots ] به جای یکی از موارد موجود در بالا. سپس فقط می توانید پنج شماره اول فیبوناچی ، یعنی (0،1،1،2،3 ) را پیدا کنید. بنابراین پاسخ شما این خواهد بود که قبل از خاموش شدن الگوی ، 4 عدد فیبوناچی مثبت وجود دارد.

• جایزه: این را تعمیم دهید.
• مشکل دانیل لیو را که از این مشکل الهام گرفته است ، امتحان کنید.

خواص قابل تقسیم

از هویت (1) در بالا می توان استفاده کرد تا نشان دهد که اگر (a | b ) ، سپس (f_a | f_b ). در واقع ، بیشتر درست است:

این از (1) و فرایندی مشابه الگوریتم اقلیدسی است. بنویسید (a = bq+r ، ، 0 le r

توجه داشته باشید که این بحث حاکی از آن است که اگر (f_p ) اصلی باشد ، سپس (p ) اصلی یا (p = 4 ) است. Converse درست نیست ((f_2 = 1 ، f_ = 37 cdot 113) ، ) و در واقع مشخص نیست که آیا بی نهایت بسیاری از حقوقی (p ) وجود دارد به گونه ای که (f_p ) اصلی است.

پاسخ خود را ارسال کنید

In the Fibonacci sequence, (F_=1), (=1), and for all (N>1 ) ، (f_n = f_+f_ ).

چه تعداد از اولین اصطلاحات فیبوناچی 2014 در 0 به پایان می رسد؟

قضیه Zeckendorf

نمایش Zeckendorf از یک عدد صحیح مثبت ، بیان عدد صحیح به عنوان مجموع (حداقل یک) اعداد فیبوناچی غیر متوالی متمایز است. به عنوان مثال ، (41 = 34+5+2 ) بازنمایی Zeckendorf از (41 ) است.

هر عدد صحیح مثبت دقیقاً یک نمایش Zeckendorf دارد.

برای اولین بار که نمی تواند بیش از یک نمایندگی وجود داشته باشد ، از هویت های موجود در مورد (3) در بالا استفاده کنید تا ببینید که مجموع هر شماره فیبوناچی غیر متوالی که بزرگترین آنها (f_n ) نمی تواند بزرگتر از باشد (F_)) (() توجه داشته باشید که (f_1 ) و (f_3 ) اعداد فیبوناچی متوالی هستند زیرا (f_1 = f_2). ) سپس فرض کنید که دو نمایش Zeckendorf از یک عدد صحیح وجود دارد و همه را کم می کنداعداد فیبوناچی مشترک در دو مبلغ. سپس دو مبلغ حاصل هنوز هم برابر هستند و از دو مجموعه جدا شده از اعداد فیبوناچی تشکیل شده است. فرض کنید بزرگترین شماره فیبوناچی در مبلغ اول (f_a ) و بزرگترین شماره فیبوناچی در مبلغ دوم (f_b ) است. فرض کنید بدون از دست دادن کلی بودن که (الف)

برای دیدن اینکه نمایندگی Zeckendorf همیشه وجود دارد ، با القاء ادامه می یابد. مورد پایه روشن است ((1 = 1،2 = 2) ، ) و اکنون فرض کنید نتیجه برای همه (k) نگه داشته شده است

این اثبات حاکی از آن است که با استفاده از بزرگترین عدد فیبوناچی کمتر از (n ، ) که آن را از بین می برد ، می توان نمای Zeckendorf را پیدا کرد.

این قضیه کاربردی در تئوری برنامه نویسی دارد.