Are they in the same sequence?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Are they in the same sequence?

Postby Scigatt » Wed May 27, 2015 4:01 am UTC

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?

Postby Tirian » Wed May 27, 2015 5:06 pm UTC

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
...

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

Re: Are they in the same sequence?

Postby eta oin shrdlu » Fri May 29, 2015 7:40 pm UTC

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: No registered users and 9 guests