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


در ریاضیات، اعداد فیبوناچی که اغلب با $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$ امین عنصر این دنباله وجود دارند. مهم‌ترین آن‌ها عبارتند از:


==== حل‌ با توابع بازگشتی ====

<code cpp>
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
</code>


=== تحلیل پیچیدگی زمانی ===


$$
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)$




==== حل‌ با استفاده از دو متغیر اضافی ====

<code cpp>
a = 0
b = 1
for i := 2 to n:
    a, b = b, a + b
</code>


=== تحلیل پیچیدگی زمانی ===
این الگوریتم یک حلقه از $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$ دانش‌آموز دارد که در صبحگاه در یک صف به ترتیب پشت سر هم می‌ایستند. مدرسه میخواهد تعدادی از این دانش‌آموزان (حداقل یک نفر)‌ را برای گروه سرود انتخاب کند که در آن هیچ دو دانش‌آموزی که در صف پشت سر هم هستند نباشند. مدرسه چند راه برای انتخاب این گروه دارد؟

<پاسخ>
سوال را برای $n$ دانش آموز حل می‌کنیم. فرض می‌کنیم جواب مساله برای $n$ دانش‌آموز برابر $s_n$ باشد. برای $n = 1$، تنها ۱ راه وجود دارد، پس $s_1 = 1$. برای $n = 2$، تنها‌ یکی از دانش‌آموزان می‌تواند در گروه سرود باشد، پس ۲ راه وجود دارد، پس $s_2 = 2$.
برای $n$ های بزرگ‌تر از $2$: اگر دانش‌آموز آخر (شماره‌ی $n$)، در گروه سرود باشد، دانش آموز $n-1$ ام نمی‌تواند باشد، پس $s_{n-2}$ راه وجود دارد، و اگر نباشد، $s_{n-1}$ راه. بنابر‌این: $s_n = s_{n-1} + s_{n-2}$. می‌توان دید که $s_n = f_{n+1}$. پس جواب مساله برابر است با $f_{13}$ یعنی $233$.
</پاسخ>