Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
It looks like $a_n$ will be $\Omega(n)$ bits long. –  Sean Eberhard Sep 5 '12 at 9:43
9  
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. –  Euclidean Sep 5 '12 at 9:53
2  
@martini why don't you post it as answer. –  Euclidean 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
show 1 more comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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