2

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?

develarist
  • 1,514
user3038404
  • 121
  • 1
    Mh, nothing better than "linear recurrence of the second order with constant coefficients and constant right-hand side". Lirsococorhas ? –  Dec 03 '20 at 10:38
  • See: https://en.wikipedia.org/wiki/Linear_difference_equation . There is a bit of theory related to those "linear difference equations", especially if they are with constant coefficients. –  Dec 03 '20 at 10:39
  • Well, the case $a=n,b=1,c=0$ generates what we call the metallic means, in the sense that the $n$th metallic mean is the limit of the ratio of consecutive terms (in the same way the golden ratio is that for the Fibonacci numbers). This "$N$-generated Fibonacci sequence" may also be in line with what you want -- https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#N-generated_Fibonacci_sequence – PrincessEev Dec 03 '20 at 10:40
  • 2
    If $c=0$ then you have a Lucas sequence. – PM 2Ring Dec 03 '20 at 10:44
  • Sorry my bad, I edited the question. "where: a >0 , b >0 and c>0". – user3038404 Dec 03 '20 at 10:48

2 Answers2

3

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:

  1. 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) $$

  2. 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}$

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

  4. 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,

  1. 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} $$

  2. 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} $$

PierreCarre
  • 20,974
  • 1
  • 18
  • 34
  • One has to take care a bit when there are roots of higher multiplicity (i.e., when $a^2+4b=0$: In that case we combine $\lambda^n$ and $n\lambda^n$ instead of $\lambda_1^n$ and $\lambda_2^n$. -- In the OP situation, this exception is prevented by the condition $a,b>0$. – Hagen von Eitzen Dec 03 '20 at 13:35
  • 1
    @HagenvonEitzen I did state that before I wrote down the general solution of the homogeneous equation. In any case, for the sake of completeness, I added the other possible situations. – PierreCarre Dec 03 '20 at 13:58
0

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.

G Cab
  • 35,272