7
$\begingroup$

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.

  • 0
    @Belgi Will write an answer as Ravi suggested.2012-09-05

1 Answers 1

7

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.