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.

$\endgroup$
6
  • $\begingroup$ It looks like $a_n$ will be $\Omega(n)$ bits long. $\endgroup$ Sep 5, 2012 at 9:43
  • 9
    $\begingroup$ 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 $\endgroup$
    – martini
    Sep 5, 2012 at 9:46
  • $\begingroup$ @martini thanks. $\endgroup$ Sep 5, 2012 at 9:53
  • 2
    $\begingroup$ @martini why don't you post it as answer. $\endgroup$ Sep 5, 2012 at 10:09
  • $\begingroup$ @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 ? $\endgroup$
    – Belgi
    Sep 5, 2012 at 10:33

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .