Take the 2-minute tour ×

I've been considering this sequence:


I've generated the sequence from the rule

$$V_n=\sum_{0\leq i \lt n} V_i$$ $$V_0=1; V_1=2V_0=V_0+V_0$$

What interests me most, is that this sequence - with its rule requiring the sum of a finite, but unbounded, number of components is remarkably similar to a sequence with a local generation rule requiring doubling of the preceding value. In fact, given a reversed finite leftmost subsequence, an arbitrarily long prefix could suggest that the sequence was the reverse of one generated by a local rule (i.e. $V_n=2V_{n-1}|n\ge1$) and the discrepancy would only become apparent at the penultimate value.

It strikes me that this observation should be relevant to all empirical study... as it demonstrates how two fundamentally different underlying models can generate identical values for an infinite number of tests... and that, unless the single critical comparison (between $V_1$ and $V_2$) is made, an inappropriate model can appear to be supported.

Obviously, there are variants on this theme with different values for $V_0$ and $V_1$ - and each stabilises by $V_4$ to match a local doubling rule... and that $V_0=0$ the result is a constant sequence ($V_i=V_1|i\neq0$)... and that even when I chose $V_1\ge V_0$ I see a similar 'anomaly'.

I'm interested to discover other sequences which, when reversed, can appear to have arisen from a different recurrence relations for an arbitrarily large prefix. For example, are there neat sequences that have two equivalent recurrence relations only for elements after the fifth or later value?

share|improve this question

closed as too localized by Andreas Blass, Mark Sapir, José Figueroa-O'Farrill, Andy Putman, Loop Space Oct 31 '11 at 14:05


2 Answers 2

up vote 0 down vote accepted

Of course, yes. Take some fraction $\frac{f}{g}$ ($f$ and $g$ are polynomials) and build its recurrent sequence. Further, take $\frac{f}{g}+h$ ($h$ is a polynomial of degree 4) and do the same.

share|improve this answer
I think I follow what you're suggesting... though you're approaching the question from a different angle. The distinction I'd draw is that where your second generator polynomial is (f/g)+h, it is syntactically obvious that only the first Order(h) terms will differ from (f/g). What I found interesting about the sequence is that it could be generated from two syntactically distinct rules - one requiring finitely many operations, the other a number linear in i for each V_i. Maybe I should have asked what (simple) recurrence relations have generator functions of the form (f/g) and (f/g)+h? –  aSteve Oct 31 '11 at 12:54

Search in OEIS Returns 3 results.

Most likely apart from the initial term it is A042950

G.f.: (2-x)/(1-2*x)
a(n)=2*a(n-1), n>1; a(0)=2, a(1)=3. 
share|improve this answer
I'd found the OEIS page - I should have included a link to it... However, from comments about A042950, its most interesting property (in my view - i.e. that a fold operation over prefixes generates a sequence very similar, but not identical to, one with only a local rule) does not seem to be discussed. Significantly, I can't see a way to find other (simply generated) sequences in OEIS that have a similar property. –  aSteve Oct 31 '11 at 13:00
