اعداد فیبوناچی

در ریاضیات، اعداد فیبوناچی که اغلب با $F_n$ نمایش داده می‌شود، دنباله‌ای نامتناهی از اعداد حسابی‌ است که در آن هر عنصر حاصل جمع دو عنصر پیشین خود است.

$$ F_n = \begin{cases} 0 & \mbox{if } n = 0; \\ 1 & \mbox{if } n = 1; \\ F_{n-1} + F_{n-2} & \mbox{if } n> 1. \\ \end{cases} $$ بدین معنی که: عنصر صفرم یعنی $F_0$ برابر با صفر، عنصر اول یعنی $F_1$ برابر با یک،‌ و عنصر $n$ ام یعنی $F_n$ که $n > 1$ برابر است با مجموع عنصر $n-1$ ام و عنصر $n-2$ ام.

عناصر اولیه‌ی این دنباله عبارتند از: $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...$$

راه حل‌ها و الگوریتم‌های زیادی برای محاسبه $n$ امین عنصر این دنباله وجود دارند. مهم‌ترین آن‌ها عبارتند از:

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

$$ T(n) = \begin{cases} 1 & \mbox{if } n = 0 \mbox{ or } n = 1; \\ T(n-1) + T(n-2) & \mbox{if } n> 1. \\ \end{cases} $$

با استقرای ریاضی می‌توان نشان داد که: $T(n) = O(2^n)$

زیرا: $T(n) = T(n-1) + T(n-2) = O(2^{n-1}) + O(2^{n-2}) = O(2^n)$

a = 0
b = 1
for i := 2 to n:
    a, b = b, a + b

این الگوریتم یک حلقه از $2$ تا $n$ دارد،‌بنابراین پیچیدگی زمانی آن $O(n)$ است.

اگر ماتریس $A$ و $M$ برابر باشند با: $$A = \begin{bmatrix}F_{n-1} \\ F{n} \end{bmatrix}$$ و $$M = \begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}$$

با استفاده از تعریف ریاضی اعداد فیبوناچی می‌توان نشان داد که: $$M \times A = \begin{bmatrix}F_{n} \\ F{n+1} \end{bmatrix}$$

بدین ترتیب برای $0 \leq n$ داریم: $$M^n \times A = \begin{bmatrix}F_{n} \\ F{n+1} \end{bmatrix}$$

پس برای به‌دست آوردن $F_n$ کافی‌ است $M^n$ را محاسبه کرده، آن را در ماتریس $A$ ضرب کنیم و عنصر واقع در ستون اول سطر اول ماتریس حاصل را بگیریم.

با استفاده از توابع مولد می‌توان نشان داد: $$F_n = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n)$$

مثال: کلاسی $12$ دانش‌آموز دارد که در صبحگاه در یک صف به ترتیب پشت سر هم می‌ایستند. مدرسه میخواهد تعدادی از این دانش‌آموزان (حداقل یک نفر)‌ را برای گروه سرود انتخاب کند که در آن هیچ دو دانش‌آموزی که در صف پشت سر هم هستند نباشند. مدرسه چند راه برای انتخاب این گروه دارد؟