Finding the solution to the recurrence relation

Question

Please help me prove which {aⁿ} is the solution to the recurrence relation a_n = 2a_n-1 - a_n-2.

a) a_n = -5ⁿ

b) a_n = 5^-n

c) a_n = 5ⁿ

d) none of the above

Please provide solution. I want to know how to get the solution too. Thank you so much!

Answer 1

In order to find a specific solution, as this is a recurrence relationship, you must also be provided with 2 values, for example, a₁ and a₂

Thus, the answer is none of the above.

We would normally find the eigenvalues of the 1-step transition matrix from (a_n-1 a_n) to (a_n a_n+1) =

0 1

-1 2

(Note that the bottom row is the recurrence, and the top row carries the value of an from the first vector to the second)

However, when we solve this equation, we get

(0 - λ)(2 - λ) - 1(-1) =0

λ² - 2λ + 1 =0

(λ - 1)² = 0

λ = 1

When we have distinct eigenvalues λ₁ and λ₂ , our solution is

an = Cλ₁ⁿ + Dλ₂ⁿ , where C and D are constants that are solved for based upon the initial values

However, when you have 2 eigenvalues that are the same, as in this case, the solution is

an = Cλⁿ + Dnλⁿ (if you had a triple root, you would have an n² term, for a quadruple root an n³ term added, etc.)

In the case of this specific problem, λ = 1, so our solution is

an = C1ⁿ + Dn1ⁿ, or

a_n = C + Dn

This, of course, is an arithmetic progression.

Another way of showing this:

a_n = 2a_n-1 - a_n-2

a_n - a_n-1 = 2a_n-1 - a_n-2 - a_n-1

a_n - a_n-1 = a_n-1 - a_n-2

Our differences are constant, which defines an arithmetic progression.

Now, if we had been given a₁ and a₂ , D = a_{2 -} a₁

Then, as a₁ = C + D(1) = C + D

C = a₁ - D = a₁ - (a_{2 -} a₁) = 2a₁ - a₂

Our solution is a_n = C + Dn, where C = 2a₁ - a₂ and D = a_{2 -} a₁

Answer 2

Try substituting in

(c) a_n = 2a_n-1 - a_n-2, so 5ⁿ = 2 . 5 ^n-1 - 5^n-2

so 25 = 2.5 - 1 clearly untrue

(b) 5^-n = 2,5^-n+1 - 5^-n+2

1 = 2.5 - 25 clearly untrue

(a) same as c, but sign has changed, so untrue

(d) is the answer

If you are given a₀ (in some cases) you can derive an expression for a_n