The Fibonacci sequence is defined as

$[0, 1, 1, 2, 3, 5, 8, \dots]$ are the first few members to the sequence.

In a simple attempt to generate the Fibonacci number at a index i, we may consider

int Fibonacci(int i) {
    if(i == 0) {
        return 0;
    } else if(i == 1) {
        return 1;
    }
    return Fibonacci(i - 1) + Fibonacci(i - 2);
}

However, this approach is very slow; the time complexity is $O(2^n)$. It would take about 10^15 iterations to return a fibonacci number at index 50.

A better algorithm is to cache the numbers that have been generated which will significantly improve the complexity.

long Fibonacci_Cache(int i) {
    // cache variable to memorize last step
    long two_before = 0;
    long one_before = 1;
    // base case
    if(i == 0) {
        return 0;
    } else if(i == 1) {
        return 1;
    }
    long current;
    for(int index = 0; index < i - 1; index++) {
        // new F_index
        current = two_before + one_before;
        // assign new F_index to the cache variable
        two_before = one_before;
        one_before = current;
    }
    return current;
}

Alternatively, according to [1], the fibonacci number at index i can be represented by

Where $\Phi \approx 1.61803$ is the golden ratio and $\hat \Phi \approx -0.61803$. Using that, we can calculate the fibonacci number at index 10

we can verify by running

int main() {
    int number = 10;
    printf("Fibonacci number for index: %d is %ld\n", number, Fibonacci_Cache(number));
}

Fibonacci number for index: 10 is 55

Putting the formula in c code, we get a function that can return a fibonacci number using golden ratio!

long Fibonacci_Num(int i) {
    double golden_ratio = (1.0 + sqrt(5)) / 2.0;
    double golden_conj = (1.0 - sqrt(5)) / 2.0;
    // round because of rounding error from calculation
    return roundl((pow(golden_ratio, (double) i) - pow(golden_conj, (double) i)) / sqrt(5));
}

int main() {
    int number = 10;
    printf("Fibonacci number for index: %d is %ld\n", number, Fibonacci_Num(number));
}

Fibonacci number for index: 10 is 55

However, note that due to rounding error and loss of accuracy in double data type, the number returned may be off a bit when the index is large; let's say for $F_{80}$.

To prove that this formula is correct, we can use proof by induction.

To recap, fibonacci number is defined by

We want to prove that

where the golden ratio $\Phi$ and its conjugate $\hat \Phi$ are defined by

First, we prove the initial case that

Thus the initial case is true

Assume that

and

are both true, we want to prove that

By the definition of fibonacci sequence.

Comparing equation (1) and (2), they would be equal if $\Phi + 1 = \Phi ^2$ and $\hat \Phi + 1 = \hat \Phi ^2$

Similarly,

Thus replacing $\Phi^2 = \Phi + 1$ and $\hat \Phi^2 = \hat \Phi + 1$ to the equation (2),

Thus by induction, we prove that