Solve the recurrence relation

Question

Solve the recurrence relation 𝑎_n=3𝑎_n-1+2 where 𝑎₁=1. (That is, provide a closed formula for the sequence.)

Answer 1

the sequence is 1, 5, 17, 53, 161, 485

a2 = 3a1 + 2

a3 = 3a2 + 2

= 3 (3a1 + 2) + 2

= 3^2 a1 + 3*2 + 2

a4 = 3 a3 + 2

= 3 ( 3^2 a1 + 3*2 + 2 ) +2

= 3^3 a1 + 3^2*2 * 3*2 + 2

a5 = 3 (a4) + 2

= 3 ( 3^3 a1 + 3^2 * 3*2 + 2 ) + 2

= 3^4 a1 + 3^3*2 + 3^2*2 * 3*2) + 2

a6 = 3 ( a5) + 2

= 3 ( 3^4 a1 + 3^3 + 3^2 * 3*2))

= 3^5 a1 + 3^4*2 + 3^3*2 + 3^2*2 +3* 2) +2

the coefficient of a1 is 3^(n-1)

the constant term is a geometric sequence with r=3 and constant k=2,

and the leading term has exponent TWO (2) behind the index..

Sum of the first k terms of the geometric sequence is [r^(k+1) - 1]/ (r-1) with k=n-2 ---> k+1=n-1

2(3^(n-1 - 1))/(3-1)

= 3^(n-1) - 1 <--- 2 in the denominator cancels the 2 * 3^(n-1)

and -2 in the numerator

adding these two pieces together

2*3^(n-1) - 1

which for n=1,2,3,...., produce the sequence 1,5,17,53,161,485

Answer 2

One solution is to simply look at the pattern a2 = 5, a3 = 17, a4 = 53, a5 = 161 and see that they all follow the pattern an = 2 * 3^(n-1) - 1, then prove that the recursion works with this.

an+1 = 3 * (2 * 3^n-1 -1) + 2 = 2*3^n - 3 + 2 = 2*3^n - 1

Also, a2 = 3 * a1 + 2

a3 = 3 * (3 * a2 + 2) + 2 = 3^2*a1 + 3 * 2 + 2

a4 = 3 * (3 * a3 + 2) + 2 = 3 * (3^2*a1 + 3 * 2 + 2) + 2 = 3^3 * a1 + 3^2 * 2 * 3 * 2 + 2

a5 = 3 * (3^3 * a1 + 3^2 * 2 * 3 * 2 + 2) + 2 = 3^4 * a1 + 3^3 * 2 + 3^2 * 2 + 3 * 2 + 2

Thus, an = 3^(n-1) * a1 + 3^(n-2)*2 + 3^(n-2)*2 + ... + 2

If we start from 2, we have a ratio of 3 and n-1 terms

the expression for this is a (1 - r^(n-1))/1-r, where a is the first term and r is the ratio.

The sum is 2 (1 - 3^(n-1))/(1-3) = 3^(n-1) - 1

Thus, our sum is 3^(n-1) * a1 + 3^(n-1) - 1; as a1 = 1, the sum is 2 * 3^(n-1) - 1