What is the name of Fibonacci variation when $F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$, were $c$ is a constant, and $a >0, \ b >0, \ c>0$ I am trying to write $\log(n)$ algorithm for the above. I don't know if there is a specific name for the Fibonacci variation when:
$$F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$$
where: $a >0, \ b >0, \ c>0$
Could someone help me with the name of this variation?
 A: For general coefficients $a,b,c$ what you have is a linear second order difference equation with constant coefficients and constant RHS. I'm not sure what is your algorithm, but you can get a closed form expression for $F_n$ by following these steps:

*

*Compute the general solution of the homogeneous equation $F_n = aF_{n-1}+bF_{n-2}$. This is accomplished knowing the roots of the characteristic equation $p(\lambda) = \lambda^2 - a\lambda -b$. In this case ($a,b>0$) the solution is
$$
F^h_n = c_1 \left(\frac{a+\sqrt{a^2+4b}}{2}\right)^n + c_2 \left(\frac{a-\sqrt{a^2+4b}}{2}\right)^n.
$$
This solution is valid, more generally, if $a^2 + 4b>0$. If $a^2+4b = 0$, $p(\lambda)$ has a real root with multiplicity 2 and the solution would be
$$
F_n^h = (c_1 + c_ 2 n)\left(\frac a2 \right)^n
$$
Finally, if $a^2 + 4b < 0$, say $a^2+ 4b = -\beta^2 (\beta > 0)$, there are two complex conjugate roots of $p(\lambda)$ and
$$
F_n^h = \left(\frac a2\right)^n \left(c_1 \cos \left(\frac{\beta n}{2}\right) + c_2 \sin\left(\frac{\beta n}{2}\right)\right)
$$


*Obtain a particular solution of the equation, $F_n^*$. If $a+b \ne 1$ you can take $F_n^* = \frac{c}{1-a-b}$. If $a+b = 1$, you can use $F_n^* = \frac{2c n}{a}$


*The general solution to the recurrence is
$$
F_n = F_n^h + F_n^*
$$


*If you are given some extra conditions, for instance the values of $F_1$ and $F_2$, you can compute $c_1, c_2$.
In conclusion, in this particular situation,

*

*If $a+b \ne 1$
$$
F_n = c_1 \left(\frac{a+\sqrt{a^2+4b}}{2}\right)^n + c_2 \left(\frac{a-\sqrt{a^2+4b}}{2}\right)^n + \frac{c}{1-a-b}
$$


*If $a+b=1$,
$$
F_n = c_1 \left(\frac{a+\sqrt{a^2+4b}}{2}\right)^n + c_2 \left(\frac{a-\sqrt{a^2+4b}}{2}\right)^n + \frac{2c n}{a}
$$
A: Understanding that the function is null for negative $n$
$$
F(n) = aF(n - 1) + bF(n - 2) + c\quad \left| {\;F(n < 0) = 0} \right.
$$
so that its first values are
$$
\left\{ \matrix{
  F(0) = c \hfill \cr 
  F(1) = \left( {a + 1} \right)c \hfill \cr 
  F(2) = \left( {a\left( {a + 1} \right) + b + 1} \right)c \hfill \cr 
  F(3) = \left( {a\left( {a\left( {a + 1} \right) + b + 1} \right)
 + b\left( {a + 1} \right) + 1} \right)c \hfill \cr 
  \quad \quad  \vdots  \hfill \cr}  \right.
$$
then its o.g.f. will be derived as
$$
\eqalign{
  & G(z) = \sum\limits_{0\, \le \,n} {F(n)z^{\,n} }  =   \cr 
  &  = a\sum\limits_{0\, \le \,n} {F(n - 1)z^{\,n} }  + b\sum\limits_{0\, \le \,n} {F(n - 2)z^{\,n} }
  + c\sum\limits_{0\, \le \,n} {z^{\,n} }  =   \cr 
  &  = az\sum\limits_{1\, \le \,n} {F(n - 1)z^{\,n - 1} }
  + bz^{\,2} \sum\limits_{2\, \le \,n} {F(n - 2)z^{\,n - 2} }
  + c{1 \over {1 - z}} \cr} 
$$
which gives
$$
\eqalign{
  & G(z) = {c \over {\left( {1 - z} \right)\left( {1 - az - bz^{\,2} } \right)}}
 = {{c/b} \over {\left( {z - 1} \right)\left( {z^{\,2}  + {a \over b}z - {1 \over b}} \right)}} =   \cr 
  &  = {{c/b} \over {\left( {z - 1} \right)
\left( {z - \left( { - {a \over {2b}} + \sqrt {a^{\,2}  + 4b} } \right)} \right)
\left( {z - \left( { - {a \over {2b}} - \sqrt {a^{\,2}  + 4b} } \right)} \right)}} =   \cr 
  &  = {{c/b} \over {\left( {z - 1} \right)\left( {z - r} \right)\left( {z - s} \right)}} =   \cr 
  &  = {c \over b}\left( {{1 \over {\left( {s - 1} \right)\left( {s - r} \right)\left( {z - s} \right)}}
 + {1 \over {\left( {r - s} \right)\left( {r - 1} \right)\left( {z - r} \right)}}
 + {1 \over {\left( {r - 1} \right)\left( {s - 1} \right)\left( {z - 1} \right)}}} \right) =   \cr 
  &  =  - {c \over b}
\left( {{1 \over {s\left( {s - 1} \right)\left( {s - r} \right)\left( {1 - {z \over s}} \right)}}
 + {1 \over {r\left( {r - s} \right)\left( {r - 1} \right)\left( {1 - {z \over r}} \right)}}
 + {1 \over {\left( {r - 1} \right)\left( {s - 1} \right)\left( {1 - z} \right)}}} \right) \cr} 
$$
Therefore $F(n)$ will be
$$
F(n) = {A \over {s^{\,n} }} + {B \over {r^{\,n} }}
 +C
$$
which is valid for $r$ and $s$ even complex, provided that they are not such as to
make null one of the denominators above.
