509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n – 1) + F(n – 2), for n > 1.

Given n, calculate F(n).

Do you know Fibonacci numbers? Guess: F(n) = 1.5 * F(n-1).

The Golden Ratio

If the coefficient is 1.5, the list is 2, 3, 5, 8, 12. 12 is incorrect.

Probabaly the coefficient 1.5 is inaccurate. What’s the real coefficient? Let \(r=\frac{f_n}{f_{n-1}}\) for n>1.

$$
\begin{align*}
r &= \frac{f_n}{f_{n-1}} \\
r &= \frac{f_{n-1}+f_{n-2}}{f_{n-1}}\\
r &=1+\frac{f_{n-2}}{f_{n-1}} \\
r &= 1+\frac{1}{r} \\
r^2 &= r + 1 \\
\end{align*}
$$

The discriminant of the quadratic equation \(\Delta =1-4*(-1)=5 >0\), so there are two distinct roots. Hence, \(r_1=\frac{1-\sqrt{5}}{2}\) and \(r_2=\frac{1+\sqrt{5}}{2}\).

\(r_1\) is less than 0, so the ratio is \(r_2\).

Therefore, the calculated sequence is 1, 1, 2, 3, 4, 7, … \(f_4\) is incorrect, which should be 5 rather than 4.

Precaculated Result

Because \(f_4\) is incorrect, we can store the result in the program, and write Listing .

public int Fib(int n)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return 1;

	if (n == 4)
		return 5;

	return (int)Math.Pow((1 + Math.Sqrt(5)) / 2, n);
}

Yet, there are still differences between the calculated numbers with the actual numbers. You could reach a solution of Listing ^[1].

public int FibPrecaculated(int n)
{
	int[] fib_nums = {
		0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
		6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
		1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
		102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};

	return fib_nums[n];
}

Study Errors

\(3\times \frac{1+\sqrt{5}}{2} \approx 4.85 \neq 5\). Let’s define the error \(e_n=f_n-\frac{1+\sqrt{5}}{2}f_{n-1}\).

$$
\begin{align*}
e_n &= f_n-\frac{1+\sqrt{5}}{2}f_{n-1} \\
e_n &= f_{n-1}+ f_{n-2} -\frac{1+\sqrt{5}}{2}f_{n-1} \\
e_n &=\frac{1-\sqrt{5}}{2} f_{n-1}+ f_{n-2} \\
e_n &=\frac{1-\sqrt{5}}{2} (f_{n-1}+ \frac{2}{1-\sqrt{5}} f_{n-2}) \\
e_n &=\frac{1-\sqrt{5}}{2} (f_{n-1}+ \frac{2(1+\sqrt{5})}{(1-\sqrt{5})(1+\sqrt{5})} f_{n-2}) \\
e_n &=\frac{1-\sqrt{5}}{2} (f_{n-1} – \frac{1+\sqrt{5}}{2} f_{n-2}) \\
e_n &=\frac{1-\sqrt{5}}{2} (e_{n-1}) \\
\end{align*}
$$

It turns out e is a geometric sequence with ratio \(\frac{1-\sqrt{5}}{2}\) for n>=2, and \(e_2=f_2-rf_1= 2 – \frac{1+\sqrt{5}}{2} = \frac{3-\sqrt{5}}{2}\), and \(e_n=\left(\frac{1-\sqrt{5}}{2}\right)^{n-2} \frac{3-\sqrt{5}}{2}\) (n>=2).

$$
\begin{align*}
f_n &= \frac{1+\sqrt{5}}{2}f_{n-1}+e_n \qquad (n\geqslant 2)\\
f_n &= \frac{1+\sqrt{5}}{2}f_{n-1}+ e_n \\
f_n &= \frac{1+\sqrt{5}}{2}\left (\frac{1+\sqrt{5}}{2}f_{n-2}+ e_{n-1} \right )+ e_n \\
f_n &= \frac{1+\sqrt{5}}{2}\left (\frac{1+\sqrt{5}}{2}\left (\frac{1+\sqrt{5}}{2}f_{n-3} + e_{n-2} \right )+ e_{n-1} \right )+ e_n \\
f_n &= \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} f_2 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} e_2 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-3} e_3 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-4} e_4 + \cdots + \left (\frac{1+\sqrt{5}}{2} \right )^{n-n} e_n \\
\end{align*}
$$

We know \(f_2 = 2\). Then we study the remaining parts E.

$$
\begin{align*}
E =& \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} e_2 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-3} e_3 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-4} e_4 + \cdots + \left (\frac{1+\sqrt{5}}{2} \right )^{n-n} e_n \\
=& \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} e_2 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-3} \frac{1-\sqrt{5}}{2} e_2 + \left (\frac{1+\sqrt{5}}{2} \right )^{n-4} \left (\frac{1-\sqrt{5}}{2} \right )^2 e_2 + \cdots + \left (\frac{1+\sqrt{5}}{2} \right )^{n-n} \left (\frac{1-\sqrt{5}}{2} \right )^{n-2} e_2 \\
=& e_2 \left (\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} + \left (\frac{1+\sqrt{5}}{2} \right )^{n-3} \frac{1-\sqrt{5}}{2} + \left (\frac{1+\sqrt{5}}{2} \right )^{n-4} \left (\frac{1-\sqrt{5}}{2} \right )^2 + \cdots + \left (\frac{1+\sqrt{5}}{2} \right )^{n-n} \left (\frac{1-\sqrt{5}}{2} \right )^{n-2} \right ) \\
\end{align*}
$$

By observation, we know the next term is \(\frac{1-\sqrt{5}}{1+\sqrt{5}}\) times the previous term.

$$
\begin{align*}
E=& e_2 \left (\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} + \left (\frac{1+\sqrt{5}}{2} \right )^{n-3} \frac{1-\sqrt{5}}{2} + \left (\frac{1+\sqrt{5}}{2} \right )^{n-4} \left (\frac{1-\sqrt{5}}{2} \right )^2 + \cdots + \left (\frac{1+\sqrt{5}}{2} \right )^{n-n} \left (\frac{1-\sqrt{5}}{2} \right )^{n-2} \right ) \\
=& e_2 \left (\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} + \frac{1-\sqrt{5}}{1+\sqrt{5}}\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} + \left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^2\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} + \cdots + \left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-2}\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} \right ) \\
=& e_2 \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} \left (1 + \frac{1-\sqrt{5}}{1+\sqrt{5}}+ \left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^2 + \cdots + \left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-2} \right ) \\
\end{align*}
$$

The sum of a geometric series is \(\frac{a(1-r^n)}{1-r}\), and here a=1 and \(r=\frac{1-\sqrt{5}}{1+\sqrt{5}}\).

$$
\begin{align*}
f_n &=\left (\frac{1+\sqrt{5}}{2} \right )^{n-2} f_2 + E \\
&=\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} + e_2 \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} \frac{1-\left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-1}}{1-\frac{1-\sqrt{5}}{1+\sqrt{5}}} \\
&=\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} + \frac{3-\sqrt{5}}{2} \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} \frac{1-\left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-1}}{\frac{2\sqrt{5}}{1+\sqrt{5}}} \\
&=\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} + \frac{3-\sqrt{5}}{2} \left (\frac{1+\sqrt{5}}{2} \right )^{n-2} \left (\frac{1+\sqrt{5}}{2} \right ) \frac{1-\left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-1} }{\sqrt{5}} \\
&=\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} + \frac{3-\sqrt{5}}{2} \left (\frac{1+\sqrt{5}}{2} \right )^{n-1} \frac{\sqrt{5}-\sqrt{5}\left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-1} }{5} \\
&=\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} + \frac{3-\sqrt{5}}{2} \left (\frac{1+\sqrt{5}}{2} \right )^{n-1}
\frac{\sqrt{5}}{5}- \left (\frac{3-\sqrt{5}}{2} \right ) \left (\frac{1+\sqrt{5}}{2} \right )^{n-1} \frac{\sqrt{5}}{5} \left (\frac{1-\sqrt{5}}{1+\sqrt{5}} \right )^{n-1} \\
&=\left ( 1 + \frac{3\sqrt{5}-5}{10} \right )\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} – \left ( \frac{3\sqrt{5}-5}{10} \right ) \frac{\left (1+\sqrt{5} \right )^{n-1}}{2^{n-1}}\frac{\left (1-\sqrt{5} \right ) ^{n-1}}{\left (1+\sqrt{5} \right ) ^{n-1}} \\
&= \left ( \frac{3\sqrt{5}+5}{10} \right )\left (\frac{1+\sqrt{5}}{2} \right )^{n-1} – \left ( \frac{3\sqrt{5}-5}{10} \right ) \left (\frac{1-\sqrt{5}}{2} \right )^{n-1} \qquad (n\geqslant 2)\\
\end{align*}
$$

Finally, we are ready to answer the leetcode coding problem.

See also . A Proof of Binet's Formula. milefoot. [2024-06-28].

References

1. Shivansu_7. 5 Different Approach 🚀 || Full explained💯 ➡️ Java/C++/C/Python3/Rust/JavaScript. . 2024-01-18 [2024-06-28].↑