Answer to Question #349270 in Discrete Mathematics for sara

Question

Show that the explicit sequence {an} where an= 2n+1

-1 for n > or = to 1 is a

solution of the recurrence relation: an= 3an-1 – 2an-2 , n >or = to 3

Answer 1

Given $a_n=2^{n+1}-1, n\ge 1.$

Then

$$a_{n-1}=2^{n-1+1}-1=2^n-1$$

$$a_{n-2}=2^{n-2+1}-1=2^{n-1}-1$$

Substitute

$$3a_{n-1}-2a_{n-2}=3(2^n-1)-2(2^{n-1}-1)$$

$$=3(2^n)-3-2^n+2=2^{n+1}-1=a_n, n\ge 3$$

Since the last equation is true, then the explicit sequence $\{a_n\}$ where $a_n=2^{n+1}-1, n\ge 1$ is a solution of the recurrence relation:

$$a_n=3a_{n-1}-2a_{n-2}, n\ge 3$$