Solve this recurrence relation and find a2 and a3?

Question

We have to recurrence relation a_n = 2a_n-1 - a_n-2. Find a₂ and a₃ if:

 

a) a₀ = 1 and a₁= 1?

b) a₀ = 0 and a₁ = 0?

 

Answer 1

The function, a_n = 2a_n-1 - a_n-2, defines the n^th value in the sequence as a function of the two previous values.  So, the value of a₀ and a₁ are defined at the beginning and the function is valid only for n>1.

 

Note that there are two methods for defining the possible values of n:  (1) start with n=0, and (2) start with n=1.   You will find both methods used very often.

 

In order to find the value for any a_n, the two previous a_n values are used.  That means that you may have to find all of the a_n values from a₂ up to a_n-1 in order to evaluate the function to get a_n.

 

Thus, a recursive function has:

    (1)  a base case

    (2)  a recursive case

 

Part a:

      a₀ = 1      (base case)

      a₁ = 1      (base case)

      a₂ = 2a₁ - a₀ = 2(1) - 1 = 1    (recursive case)

      a₃ = 2a₂ - a₁ = 2(1) - 1 = 1    (recursive case)

 

Part b:

      a₀ = 0     (base case)

      a₁ = 0     (base case)

      a₂ = 2a₁ - a₀ = 2(0) - 0 = 0    (recursive case)

      a₃ = 2a₂ - a₁ = 2(0) - 0 = 0    (recursive case)