Since f(n) only depends on the previous two values f(n-1) and f(n-2), the sequence eventually begins to repeat itself — in this case after only a relatively small number of steps which you can work out using a simple loop.

With that in mind, you can take a loop like this which runs in O(N):

for (i: 0 -> N) {
  result += f[i % repeat] * f[(n-i) % repeat];
}

...And since the i-th iteration is the same as the (i % repeat)th iteration, turn it into a loop like this which runs in O(repeat):

for (i: 0 -> min(N, repeat - 1)) {
  result += f[i % repeat] * f[(n-i) % repeat] * (1 + (n-i) / repeat);
}