Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $ I have a recurrence relation, 
$$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ 
for $n>3$ and $a_1 = 0, a_2 = 0,  a_3 = 1$ 
I have to find the value of $a_n$ for very large values of n. I tried an approach similar to that which we use for finding the fibonacci numbers using matrix method which gives us $f_n$ in $log(n)$ time complexity. But I am not able to use it here because of the $2^{n-3}$ term. 
Can we do better than $O(n)$ time complexity.

For $n \in \mathbb N$, we let $b_n = a_n - 2^n$. We get by using the equation for $(a_n)$:
\begin{align*}
   b_n &= a_n - 2^n\\
       &= a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} - 2^n\\
       &= b_{n-1} + 2^{n-1} + b_{n-2} + 2^{n-2} + b_{n-3} + 2^{n-3} + 2^{n-3} - 2^n\\
       &= b_{n-1} + b_{n-2} + b_{n-3} + 2^{n-3}\cdot(4 + 2 + 1 + 1 - 8)\\
       &= b_{n-1} + b_{n-2} + b_{n-3},
\end{align*}
with the initial values $b_1 = -2$, $b_2 = -4$, $b_3 = -7$.
So for $(b_n)$ we got rid of the $2^{n-3}$-term and can use the same trick as for the Fibonacci numbers.
