# 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.

• It looks like $a_n$ will be $\Omega(n)$ bits long. – Sean Eberhard Sep 5 '12 at 9:43
• Hm ... let $b_n = a_n - 2^n$, then $(b_n)$ fulfills $b_n = b_{n-1} + b_{n-2} + b_{n-3}$ with $b_1 = -2$, $b_2 = -4$ and $b_3 = -7$ ... so you got rid of the $2^{n-3}$ term – martini Sep 5 '12 at 9:46
• @martini thanks. – Ravi Upadhyay Sep 5 '12 at 9:53
• @martini why don't you post it as answer. – Ravi Upadhyay Sep 5 '12 at 10:09
• @martini - it's a bit of a stupid question, but I tried to subtitue and I didn't egt that equality for $b_n$...can you show why it works ? – Belgi Sep 5 '12 at 10:33

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.