Solve this recurrence relation

Question

Solve the following recursions: $a_{n+1}=3a_n-a_{n-1}-1$ and $a_{n+1}=4a_n-a_{n-1}-1$. (These are to be solved separately, not simultaneously)

I tried using generating functions but it got messy. Any ideas?

Thanks!

Answer 1

1) Use difference equations: $$ a_n = 3 a_{n-1} -a _{n-2} -1\\ \Delta a_{n+1} = a_{n+1} - a_n\\ \Delta a_{n+1} = 3 \Delta a_{n} - \Delta a_{n-1} $$ Now for simplicity set $b_n = \Delta a_n$ and use generating function and telescoping sums.

2) same