# [seqfan] Re: An amusing paradox?

Richard Mathar mathar at strw.leidenuniv.nl
Thu Apr 7 17:49:29 CEST 2011

```http://list.seqfan.eu/pipermail/seqfan/2011-April/014757.html

This "-1" term happens with any of the initial conditions of the
recurrence. Let a(0)=a0 and a(1)=a1 be the initial terms and
all others be defined by a(n)=a(n-1)+a(n-2)+1, then
a(2) = a0+a1+1;
a(3) = a0+2*a1+2;
a(4) = 2*a0+3*a1+4;
a(5) = 3*a0+5*a1+7;
a(6) = 5*a0+8*a1+12;
a(7) = 8*a0+13*a1+20;
a(8) = 33+13*a0+21*a1;
a(9) = 54+34*a1+21*a0;
a(10) = 88+34*a0+55*a1;
a(11) = 89*a1+143+55*a0;
a(12) = 232+89*a0+144*a1;
a(13) = 376+233*a1+144*a0;
a(14) = 609+233*a0+377*a1;
a(15) = 610*a1+986+377*a0
....
a(n) = -1 + (1+a0)*F(n+1) + (a1-a0)*F(n),
= -1 + F(n+1) + a1*F(n) + a0*F(n-1),
where F(n) = A000045(n),
with generating function -1/(1-x) +(a1*x-a0*x+1+a0)/(1-x^2-x)

Supposed we define a "generalized" Fibonacci sequence without the "+1"
in the recurrence:
Fg(0)=a0
Fg(1)=a1
Fg(n) = Fg(n-1)+Fg(n+2),
with generating function
(a0+a1*x-a0*x)/(1-x-x^2) = (a1*x-a0*x-a0*x+1)/(1-x^2-x) -1/(1-x^2-x)
then
a(n) = -1 +Fg(n) -F(n-1)

If a0=a1=0 as Richard (the other one) proposed, a(n) = -1+F(n+1); in the other
cases the "-1" is well hidden by the superposition with Fg(n) and F(n-1).

RJM
Exercises: a0=1 and a1=3 gives Fg(n) = A000032(n+1) and a(n) = A001594(n+1).
Exercises: a0=1 and a1=4 gives Fg(n) = A000285(n) and a(n) = A022318(n).
Exercises: a0=1 and a1=5 gives Fg(n) = A022095(n) and a(n) = A022319(n).
etc

```