Fibonacci Sequence as Linear Recurrence

$\color{Blue}{\textbf{Learning recurrence relations- Part 1}}$

Recurrence relation is about reducing a problem to smaller problem, by finding the dependence of the $n^{th}$ term (generally denoted as $a_n$ ,the answer for a specific value $n$ given in a question) on previous terms. This gives as a recursive formula for a thing we're looking for.

$\textbf{Question}$- Find the number of ways in which a man can climb a staircase of $10$ steps, if he climbs only $1$ or $2$ steps at once.

$\textbf{Solution}$- Let $a_n$ be the number of ways in which $n$ step-staircase can be climbed. Then, we see that the man can come to the $n^{th}$ step by either taking one step from $(n-1)^{th}$ step, or by taking 2 steps from $(n-2)^{th}$ step.

And number of ways of climbing the $(n-1)$ and $(n-2)$ steps is actually $a_{n-1}$ and $a_{n-2}$.

Thus we conclude $$a_n=a_{n-1}+a_{n-2}$$

It's easy to see that 1 step can be climbed in $1$ way, and 2-step can be climbed in $2$ ways (1+1 or directly 2) , giving $a_1=1, a_2=2$.

Thus the number of ways of climbing 3-step will be $$a_3=a_1+a_2=3$$ for 4-step will be $$a_4=a_3+a_2=5$$ and so on... Thus the sequence will be $1,2,3,5,8,13,21,34,55,89,...$ And here speciically, the $10^{th}$ term is $89$, so our asked answer will be $a_{10}=\boxed{89}$

Thus, generalising a problem makes it easy at times !

Look for the coming parts of this, I'll be posting notes about Recurrence relations...

Problem 1: If there are $n$ steps to reach success and each time you may climb up 1 or 2 steps, how many different ways are there for you to reach success?

Let $f(n)$ denote the number of ways for $n$ steps. Note that $f(n) = f(n-1) + f(n-2)$ and $f(0) = 1, f(1) = 1.$ Working our way up, we can determine $f(n)$ for all positive integers $n.$

Problem 2: A pair of rabbits starts to breed after they are 2 months old and produces another pair each month. Suppose a pair of newly born rabbits is placed on a desolate island. How many pairs of rabbits will be there after $n$ months, assuming no rabbits ever die?

Let's make a table!

Month & Existing pairs & Newborn pairs & Total pairs

• 1 & 1 & 0 & 1
• 2 & 1 & 0 & 1
• 3 & 1 & 1 & 2
• 4 & 2 & 1 & 3
• 5 & 3 & 2 & 5
• 6 & 5 & 3 & 8

Starting from the 3rd month, the total pairs is the number of pairs in the last month $f(n-1)$ plus the newborn pairs $f(n-2),$ since every pair two months ago gives birth to a newborn pair.

Therefore we again have $f(1) =1, f(2) = 1,$ and $f(n)=f(n-1)+f(n-2).$

Both of the above problems were examples of the Fibonacci Sequence $F,$ which is defined as $F_1=F_2=1,$ and $F_n=F_{n-1}+F_{n-2}.$

For example, $$F_3=F_2+F_1=2,$$ $$F_4=F_3+F_2=3$$ $$F_5=5,$$ and so on.

Now using your knowledge of linear recurrences, find an explicit formula for $F_n!$

Consider the generating function $$\sum_{n=0}^{\infty}F_nx^n=x+x^2+2x^3+3x^4+5x^5+\cdots.$$ If this converges, then $f(x)=\frac{x}{1-x-x^2}.$ This is easily verified using the fact that $F_n=F_{n-1}+F_{n-2}.$ Using partial fraction decomposition and the formula for geometric series yields $$\frac{x}{1-x-x^2}=\frac{\frac{1}{\sqrt{5}}}{1-(\frac{1+\sqrt{5}}{2})x}-\frac{\frac{1}{\sqrt{5}}}{1-(\frac{1-\sqrt{5}}{2})x}= \sum_{n=0}^{\infty}\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}x^n.$$ Matching up coefficients yields $$F_n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}},$$ which is known as Binet's Formula.

The Golden Ratio

Two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. For quantities $a$ and $b$ with $a>b,$ use $\varphi$ to denote this ratio, then

$$\frac{a+b}{a}=\frac{a}{b}= \varphi,\text{ or}$$ $$1+\frac{b}{a}= \frac{a}{b}= \varphi, \text{ or}$$ $$1+\frac{1}{\varphi}= \varphi,$$ which simplifies to $$\varphi^2 = \varphi + 1.$$ The golden ratio is equivalent to the positive root, $\frac{1+\sqrt{5}}{2}.$ Notice how it shows up in Binet's Formula.

From $$\varphi^2 = \varphi + 1,$$ we have $$\varphi^3 = \varphi^2 + \varphi = \varphi + 1 + \varphi = 2\varphi + 1.$$ Similarly, $$\varphi^4 = 2\varphi^2 + \varphi = 2(\varphi + 1) + \varphi = 3\varphi + 2,$$ $$\varphi^5 =3\varphi^2 + 2\varphi = 5\varphi+ 3, \text{ etc.}$$ It is true that $$\varphi ^n = F_n\varphi + F_{n-1}.$$ In addition, it can be shown that the ratio of consecutive Fibonacci numbers approaches the Golden Ratio as $n$ increases.

The golden ratio also shows up in geometry.

• A Golden Rectangle is a rectangle whose sides are in the proportion of the Golden Ratio. For example, if a rectangle has length 1 and width $\frac{1}{\varphi},$ or length $\varphi + 1,$ and width $\varphi,$ it is a Golden Rectangle.
• A Golden Triangle is an isosceles triangle whose long side and short side are the proportion of the Golden Ratio.

Now try some of the exercises!