-------- Original Message --------
Subject: On Automatic solution of recurrence relations
Date: Sat, 29 Mar 2008 12:12:29 -0500
From: Alexander Povolotsky <apovolot(a)gmail.com>
To: alessandro.zaccagnini(a)unipr.it, bagnara(a)cs.unipr.it
Dear Roberto and Alessandro,
PURRS is great ! - Many thanks for making it available online !
But could you may be consider complementing PURRS with the tool, which
would try
to figure out whether (or not) given integer sequence <with first
"few" (unknown exact number) terms constitute
"initial conditions"> is recurrence based ?
For example consider Engel
expansion of Pi:
1, 1, 1, 8, 8, 17, 19, 300, 1991, 2492, 7236, 10586,
34588, 63403, 70637, 1236467 , 5417668, 5515697, 5633167, 7458122,
9637848, 9805775, 41840855, 58408380, 213130873
Could above sequence be by any chance recurrence based ?
Best Regards,
Alexander R. Povolotsky
--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara@cs.unipr.it
Hi,
Here is the OEIS sequence description:
A136429
a(n) = sum( F(k+1)^2 F(n-k+1)^2, k = 0..n ) where F(n) = Fibonacci
number (A000045).
1, 2, 9, 26, 84, 250, 747, 2182, 6323, 18132, 51624, 146004, 410677,
1149578, 3204477, 8899502, 24634620, 67990414, 187154271, 513939214,
1408246247, 3851081256, 10512259920, 28647203880, 77946605545,
211782868754
OFFSET
0,2
FORMULA
G.f.: (1-x)^2/((1+x)^2(1-3x+x^2)^2).
Recurrence: a(n+6) = 4 a(n+5) - 10 a(n+3) + 4 a(n+1) - a(n).
AUTHOR
Emanuele Munarini (emanuele.munarini(AT)polimi.it), Apr 01 2008
So I tried PURRS
http://www.cs.unipr.it/purrs/
PURRS Demo Results
Exact solution for x(n) = -x(6+n)+4*x(5+n)-10*x(3+n)+4*x(1+n)
for the initial conditions
x(0) = 1
x(1) = 2
x(2) = 9
x(3) = 26
x(4) = 84
x(5) = 250
x(n) = -(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5
*(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n
for each n >= 0
Then I have defined sequence in PARI using close formula generated by PURRS
(21:16) gp > a(n)=-(-1)^n*n-2/5*(3/2+1/2*sqrt(5))^n+9/5*(-1)^n+4/5*(3/2+1/2*sqrt(5))^n*sqrt(5)-4/5
*(3/2-1/2*sqrt(5))^n*sqrt(5)-2/5*(3/2-1/2*sqrt(5))^n
But it doesn't even give initial conditions ... ?
(21:16) gp > a(0)
%5 = 1.000000000000000000000000000
(21:16) gp > a(1)
%6 = 2.000000000000000000000000000
(21:17) gp > a(3)
%7 = 26.00000000000000000000000000
(21:17) gp > a(4)
%8 = 63.00000000000000000000000000
(21:17) gp > a(5)
%9 = 174.0000000000000000000000000
(21:19) gp > a(6)
%10 = 443.0000000000000000000000000
Did I make a mistake in above or ... ?
Ciao,
Regards,
Alex
