# Re: This is strange, recurrence can capture regular function.

On Apr 20, 11:10 pm, Robert Israel <isr...@xxxxxxxxxxx> wrote:
On Apr 20, 12:45 am, "dillog...@xxxxxxxxx" <dillog...@xxxxxxxxx>
wrote:

hi

This is rather strange. Well, for people who already know this, it's
probably nothing. But it's the first time I see this kind of capture.
With the hint from Professor Robert Israel, I was trying to find
recurrence equations from integer sequences with multivariate
interpolation. I had only expected to find recurrences but not regular
functions.
I capture this sequence and many similar ones:

;; A000431 is strange. this kind of function gets captured by
recurrence
;; 0, 0, 0, 2, 16, 88, 416, 1824, 7680, 31616, 128512, 518656,
2084864,
;; 8361984, 33497088, 134094848, 536608768, 2146926592, 8588754944,
;; 34357248000, 137433710592, 549744803840,
;; f(n) = (4^n - n 2^(n+1))/8 for n >= 1

;; A000431-reversed 35184271425536 8796044787712 2199000186880
549744803840 137433710592 34357248000
;; f(n) = 1/16 f(n-3)^1 -1/2 f(n-2)^1 + 5/4 f(n-1)^1
;; A000431-reversed-1 8796044787712 2199000186880 549744803840
137433710592
;; f(n) = 1/16 f(n-3)^1 -1/2 f(n-2)^1 + 5/4 f(n-1)^1
;; this is unexpected, the equations actually match

Is there a simply explanation for this?
The relationship between the regular function and the recurrence
function is total mystery.

I don't know which "this" you're trying to explain.
Constant-coefficient m-term linear recurrence relations
f(n) = sum_{j=1}^m a_j f(n-j) can always be solved.
If the polynomial P(x) = x^m - sum_{j=1}^m a_j x^(m-j) has m
distinct roots r_1, ..., r_m, the solution can be written as a
function f(n) = sum_{j=1}^m c_j r_j^n, where c_j are arbitrary
constants.
The reversed sequence satisfies a recurrence relation as
well (just express f(n-m) in terms of f(n), ..., f(n+1-m)), and the
corresponding roots are (r_j)^(-1), j=1...m.

Robert Israel isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Ok, I finally got it figured out, there is no mystery here.
I usually have the sequence (forward) and it's reverse (backward) for
interpolation. Because the forward case didn't return a result, I
thought the backward sequence has return something that the forward
sequence didn't not imply. Wrong. It's simply that the sequence from
the database has some initial elements that should be ignored. In this
case, the backward sequence, happens to be captured while the forward
sequence failed. I have retried the sequence with initial element
removed, then it's captured.

Found Recurrence:
sequence: (A000431-1 0 2 16 88 416 1824 7680 31616 128512
518656 2084864 8361984 33497088 134094848 536608768 2146926592
8588754944 34357248000 137433710592 549744803840 2199000186880
8796044787712 35184271425536)
length: 23
configurations: ((3 1 8 8 19) (2 2 9 9 20) (1 10 11 11 23))
n d m v t: (3 1 8 8 19)
I b V: ((0 2 16) #(88 416 1824 7680 31616 128512 518656
2084864) (A000431-1 8361984 33497088 134094848 536608768 2146926592
8588754944 34357248000 137433710592))
pattern: ((f(n-3)^1 f(n-2)^1 f(n-1)^1) (f(n-3)^1 f(n-2)^1
f(n-1)^0) (f(n-3)^1 f(n-2)^0 f(n-1)^1) (f(n-3)^1 f(n-2)^0 f(n-1)^0)
(f(n-3)^0 f(n-2)^1 f(n-1)^1) (f(n-3)^0 f(n-2)^1 f(n-1)^0) (f(n-3)^0
f(n-2)^0 f(n-1)^1) (f(n-3)^0 f(n-2)^0 f(n-1)^0))
solution: #(0 0 0 16 0 -20 8 0)
none zero terms: (. . . (16 (f(n-3)^1 f(n-2)^0 f(n-1)^0)) . (-20
(f(n-3)^0 f(n-2)^1 f(n-1)^0)) (8 (f(n-3)^0 f(n-2)^0 f(n-1)^1)) .)
scheme: (define f (memoize (lambda (n) (cond ((= n 1) 0) ((=
n 2) 2) ((= n 3) 16) (else (+ 0 0 0 (* 16 (expt (f (- n 3)) 1) (expt
(f (- n 2)) 0) (expt (f (- n 1)) 0)) 0 (* -20 (expt (f (- n 3)) 0)
(expt (f (- n 2)) 1) (expt (f (- n 1)) 0)) (* 8 (expt (f (- n 3)) 0)
(expt (f (- n 2)) 0) (expt (f (- n 1)) 1)) 0))))))(map f (interval 1
23))
matched terms (23 out of 23 (0 2 16 88 416 1824 7680 31616 128512
518656 2084864 8361984 33497088 134094848 536608768 2146926592
8588754944 34357248000 137433710592 549744803840 2199000186880
8796044787712 35184271425536))
exact match: #t

.