Given recurrence equation :

$T(N) = T(N-1) + T(N-2) + N$

Given base case

$ T(1) = -3$

So I rewrote the equation as

$ T(n)+ n - T(1) = T(n-1)+ (n-1) - T(1) + T(n-2)+(n-2)-T(1)$

Substituting $ V(n) = T(n) + n - T(1)$ we get :

$V(n) = V(n-1) + V(n-2) $

which is the Fibonacci relation , hence :

$ T(n) = \frac{\phi^{n} - \psi^{n}}{\sqrt {5}} +n-3$

where $\phi$ is the golden ratio.

Is the substitution correct theoretically as asymptotically the constant term is dominated by the linear term ?

  • $\begingroup$ Fix the first recurrence (equivalent to $0=T(n-1)+n$) which is obviously not the intended one. $\endgroup$
    – user16034
    Sep 5 at 15:31
  • $\begingroup$ We discourage "please check my work - is it correct?" questions here, as they are unlikely to be of any use to others in the future. We are trying to build an archive of knowledge that will be useful to others. See here and here. Can you ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W.
    Sep 5 at 15:52
  • $\begingroup$ @D.W. I tried a more focused approach, is it a useful way to ask? $\endgroup$ Sep 5 at 16:11

1 Answer 1


Your substitution is correct and indeed leads to Fibonacci. Anyway the final answer does not respect $T(1)=-3$ and there is a sign error.

I would prefer to rework the recurrence independently of $T(1)$, writing


or $$U(n)=U(n-1)+U(n-2)+3$$


$$U(n)+3=U(n-1)+3+U(n-2)+3$$ and


The general solution is thus

$$V(n)=U(n)+3=T(n)+n+3=aF_n+bF_{n-1}$$ where $F_{-1}=1$.

Only now do we introduce the known initial condition $V(1)=1$, which gives $a=1$ and $b$ free.



Regarding the asymtotic behavior, we have two cases.

  • if $b\ne-\phi$, $T(n)\sim\left(1+\dfrac b\phi\right)F_n$ and the behavior is geometric of common ratio $\phi$,

  • if $b=-\phi$, the growing $\phi$ exponential cancels out and $T(n)\sim-n-3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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