If the Fibonacci numbers are given by $F_n = F_{n-1} + F_{n-2}$, find and solve a recursion for the amount of additions needed to calculate the n-th Fibonacci number.
I think i've figured out the recursion: $A(n) = A(n-1) + A(n-2) +1$. I'm just not sure how to solve this because of the +1. Am I correct in thinking that I can ignore the +1 and solve $x^2-x-1=0$?
Edit:
$a_n = a_{n-1} + a_{n-2} +1$
$a_{n+1} = a_{n} + a_{n-1} +1$
$-a_{n+1}+2a_n-a_{n-2}=0$
$-x^3+2x^2-1=0 => x=1, -0.6, 1.6$
Best Answer
For linear recurrence relations, one approach is to note that the general solution is the sum of some particular solution to the recurrence and some solution to the homogeneous recurrence. If you can solve the inhomogeneous recurrence ignoring the starting values, you can use the starting values to determine what solution to the homogeneous equation you need to add to it.
In this case, your recurrence $A(n+1)=A(n)+A(n-1)+1$ has the constant solution $A(n)=-1$, so the general solution is $A(n)=-1+a\phi^n+b\psi^n$ and you evaluate $a,b$ from the starting conditions.