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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.