## Are they in the same sequence?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Scigatt
Posts: 195
Joined: Sat Dec 23, 2006 11:45 am UTC
Location: Vancouver
Contact:

### Are they in the same sequence?

The familiar Fibonacci sequence can be extended easily to negative indices by the relation F(n-1) = F(n+1) - F(n). It is also possible to create a new (double-ended) Fibonacci-like sequence G from any ordered integer pair (a, b) by setting G(0) = a, G(1) = b, G(n) + G(n+1) = G(n+2) for all integers n. It may be the case that for two distinct integer pairs (a, b) and (c, d) that they define the same sequence with shifted indices.

Find an equation involving integers a, b, c and d that is true iff (a, b) and (c, d) define the same sequence(but perhaps shifted).

BONUS(I haven't solved this one):Find a Diophantine equation that fulfills the requirements above.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Are they in the same sequence?

Spoiler:
(a,b) and (c.d) describe the same (double-ended) sequence if and only if the simultaneous equations

c = fa + f'b
d = ga + g'b

have a solution where f' = g and (f, f', g') are consecutive members of the (canonical except maybe double-ended) Fibonacci sequence. This is not hard to see since the sequence that starts at a and then b goes:

....
1a + 0b
0a + 1b
1a + 1b
1a + 2b
2a + 3b
3a + 5b
...

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: Are they in the same sequence?

Partial solution:
Spoiler:
The expression |G(n+1)2-G(n+1)G(n)-G(n)2| is invariant for any generalized double-ended Fibonacci sequence (Cassini's identity). So |d2-dc-c2|=|b2-ba-a2| if (a,b) and (c,d) come from the same sequence. But the reverse implication doesn't always hold.
Edit 5/31 to add another approach:
Spoiler:
(a,b) and (c,d) come from the same sequence iff
n = log((c+d*φ)/(a+b*φ)) / log(φ)
is an integer (where φ is the golden ratio). If so, then n is the shift from (a,b) to (c,d).

Return to “Logic Puzzles”

### Who is online

Users browsing this forum: Google Feedfetcher and 3 guests