How to describe the sequence with general term $a_n=3^n-2^{n+1}$ with a first order constant coefficient linear relation?

Question

I know that a second order constant coefficient linear homogeneous recurrence relation can be found by considering $3$ and $2$ as the roots of the characteristic equation. But how can you write a first order constant coefficient linear recurrence relation (not necessarily homogeneous) for this?

Answer 1

Yes, you can write it into a first order constant coefficient recursion equation, but it is inhomogenous and the inhomogeneous term depends on $n$. Let $a_{n+1}=ka_n+f(n)$, since we are free to choose $k$ and $f(n)$, we let $k=3$ to satisfy your $3^n$ part, hence

$$a_{n+1}=3a_n+f(n)$$

Plut in your solution: $a_n=3^n-2^{n+1}$

$$3^{n+1}-2^{n+2}=3\cdot3^n-3\cdot2^{n+1}+f(n)\Longrightarrow f(n)=2^{n+1}$$

so we get

$$\boxed{a_{n+1}-3a_n=2^{n+1}}$$

Answer 2

You cannot! Assume that $a_n = 3^n - 2^{n+1}$ solves $a_{n+1} = ua_n + v$ for constants $u$ and $v$. Substituting $n = 0$ gives $v - u = -1$, but substituting $n = 1$ gives $v - u = 1$. Contradiction! (You can use a similar argument to show that $a_{n+k}$ cannot be the solution to a first-order linear recurrence relation either, with a little bit more work.)

Linear recurrence relations are quite similar to polynomials as you may have seen while solving them. The idea of "order" for a recurrence relation is in correspondence with "degree" for a polynomial. The idea of interpolation works similarly for both. The above argument just shows that you can't be the solution to a first-order linear equation because your value at three points cannot be solved by a first-order linear equation (similar to how you would show that a polynomial is not linear).