<s>[INST] 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?
 [/INST] 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.
</s>