Iteration for Recurrent Problem with Python

Question

I am asked to find the 30th of a recurrence series, following the equation x(n) = 2*x(n-1) - x(n-2) for n >= 3, and x(1) = 0 and x(2) = 1.

Following the logic of fibonacci iteration, I have come up with the following code:

def loop(n):
    a = 0
    b = 1
    for i in range(30):
        a, b = b, 2 * b - a
    return a

Suiting in loop(30), I am returned 30, but I know mathematically that the answer should be 29. The code seems to be going one step ahead. Can anyone help point out what is incorrect in my code?

Answer 1

You should only run the loop n - 1 times. Because the assignment a = 0 initializes x1. Then after each loop, a is assigned by the next value (from x2)

def loop(n):
    a = 0
    b = 1
    for i in range(n - 1):
        a, b = b, 2*b - a
    return a
    
print(loop(30))
# 29