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

*From*: "dillogimp@xxxxxxxxx" <dillogimp@xxxxxxxxx>*Date*: 20 Apr 2007 12:06:25 -0700

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

.

**Follow-Ups**:**Re: This is strange, recurrence can capture regular function.***From:*dillogimp@xxxxxxxxx

**References**:**This is strange, recurrence can capture regular function.***From:*dillogimp@xxxxxxxxx

**Re: This is strange, recurrence can capture regular function.***From:*Robert Israel

- Prev by Date:
**Re: Integrating tan(x)/x** - Next by Date:
**Re: College students confused about manifolds with boundary** - Previous by thread:
**Re: This is strange, recurrence can capture regular function.** - Next by thread:
**Re: This is strange, recurrence can capture regular function.** - Index(es):