[math-fun] Oddball recurrence problem
Consider the recurrence f(n) = f(n-3) + ( f(n-4) - f(n-1) ) * ( f(n-2) - f(n-1) ) / ( f(n-2) - f(n-3) ) . Initialised with integer 4-tuplets, this generates sequences which are variously periodic: 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, ...; quadratic: 3, 1, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, ...; asymptotically exponential: 1, -1, 1, -9, 49, -289, 1681, -9801, 57121, -332929, 1940449, -11309769, ...; but remarkably remain integer despite the division operator. Explain this behaviour. WFL
Let d(n) = f(n) - f(n-1). Re-writing the recurrence in terms of d(n) and simplifying yields ( d(n) + d(n-2) ) / d(n-1) = ( d(n-1) + d(n-3) ) / d(n-2) so in fact ( d(n) + d(n-2) ) / d(n-1) = C, a constant, and this is really a simpler recurrence in disguise: d(n) = C * d(n-1) - d(n-2) As long as C is an integer, you're all set (in your examples C = 1, 2 and -6, respectively). J.P. On Wed, Aug 20, 2014 at 10:09 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Consider the recurrence f(n) = f(n-3) + ( f(n-4) - f(n-1) ) * ( f(n-2) - f(n-1) ) / ( f(n-2) - f(n-3) ) . Initialised with integer 4-tuplets, this generates sequences which are variously periodic: 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, ...; quadratic: 3, 1, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, ...; asymptotically exponential: 1, -1, 1, -9, 49, -289, 1681, -9801, 57121, -332929, 1940449, -11309769, ...; but remarkably remain integer despite the division operator.
Explain this behaviour. WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Neat dispatch! I had misguidedly spent time attempting to fit second-order linear recurrences to the original sequences, before reluctantly accepting that they are actually third-order --- JPG's solution explains how my recurrences always have extra factor E-1 ( E == shift operator). The third sequence (exponential growth with alternating signs, symmetric about the -1 term) satisfies the algebraic constraints for a hyperbolic Steiner chain (intersecting frontier circles) with frontier curvatures 0,2 . However, consecutive members of this chain would touch internally --- apparently impossible in real plane geometry! So the final paragraph of my screed should be refined thus: << Geometric features of a chain, using t^2 > 0 for real n --- (6) 0 < d < 3 elliptic: A,B disjoint, incl. annular, closed; -1 < d < 0 elliptic: A,B disjoint and internal; 3 < d < oo hyperbolic: A,B intersecting; oo < d < -1 hyperbolic: infeasible in real geometry; d = 3 parabolic: Pappus arbelos, A,B touching; d = -1 degenerate: one of A,B is a point; d = oo or d = 0 impossible: eg. [1,1,1,2] ; d = 0/0 incomplete: extremum at k_(5/2) , incl. A,B concentric.
Also, the (Soddy) sample chain for n = 3 should read << [kA, kB; k1, k2, k3] = [ -1, 3; 2, 3, 2 ] , passim.
Fred Lunnon On 8/21/14, J.P. Grossman <jpg@alum.mit.edu> wrote:
Let d(n) = f(n) - f(n-1). Re-writing the recurrence in terms of d(n) and simplifying yields
( d(n) + d(n-2) ) / d(n-1) = ( d(n-1) + d(n-3) ) / d(n-2)
so in fact ( d(n) + d(n-2) ) / d(n-1) = C, a constant, and this is really a simpler recurrence in disguise:
d(n) = C * d(n-1) - d(n-2)
As long as C is an integer, you're all set (in your examples C = 1, 2 and -6, respectively).
J.P.
On Wed, Aug 20, 2014 at 10:09 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Consider the recurrence f(n) = f(n-3) + ( f(n-4) - f(n-1) ) * ( f(n-2) - f(n-1) ) / ( f(n-2) - f(n-3) ) . Initialised with integer 4-tuplets, this generates sequences which are variously periodic: 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, -3, 12, 36, 45, 30, 6, ...; quadratic: 3, 1, 1, 3, 7, 13, 21, 31, 43, 57, 73, 91, 111, 133, 157, 183, 211, 241, ...; asymptotically exponential: 1, -1, 1, -9, 49, -289, 1681, -9801, 57121, -332929, 1940449, -11309769, ...; but remarkably remain integer despite the division operator.
Explain this behaviour. WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If I can't stump the list with sequences, I shall try with chains. The classical (closed) Steiner chain comprises a small frontier circle inside a larger one, with a finite consecutively-touching cyclic sequence of circles occupying the annulus between, each also touching both frontiers. Is it possible for all circles (including both frontiers) of some (real, non-limiting, non-degenerate) chain to lie external to one another? WFL
Sure. Take three congruent mutually tangent circles, A, B, and C. Inscribe a smaller circle D so that it is externally tangent to A, B, and C. Inscribe a yet smaller circle E in the triangular void formed by A, B, and D, externally tangent to those three. Then C and E are the "frontiers", and A, B, and D form a three-circle chain between them. On Thu, Aug 21, 2014 at 6:44 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
If I can't stump the list with sequences, I shall try with chains.
The classical (closed) Steiner chain comprises a small frontier circle inside a larger one, with a finite consecutively-touching cyclic sequence of circles occupying the annulus between, each also touching both frontiers.
Is it possible for all circles (including both frontiers) of some (real, non-limiting, non-degenerate) chain to lie external to one another?
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yup. Sounds easy enough I know; but when I came across the 4-chain [ 1, 17; 2, 2, 16, 16 ] in the output from my search program, I scratched around for a while looking for a bug that (this time) wasn't there, before resorting to computing the inversion, finding the circle coordinates, and plotting the wretched thing. All good exercise to delay the irresistable march of senile decay --- or so I console myself! WFL On 8/21/14, Allan Wechsler <acwacw@gmail.com> wrote:
Sure. Take three congruent mutually tangent circles, A, B, and C. Inscribe a smaller circle D so that it is externally tangent to A, B, and C. Inscribe a yet smaller circle E in the triangular void formed by A, B, and D, externally tangent to those three. Then C and E are the "frontiers", and A, B, and D form a three-circle chain between them.
On Thu, Aug 21, 2014 at 6:44 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
If I can't stump the list with sequences, I shall try with chains.
The classical (closed) Steiner chain comprises a small frontier circle inside a larger one, with a finite consecutively-touching cyclic sequence of circles occupying the annulus between, each also touching both frontiers.
Is it possible for all circles (including both frontiers) of some (real, non-limiting, non-degenerate) chain to lie external to one another?
WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
Fred Lunnon -
J.P. Grossman