A Mathematical Journal Vol. 7, No 2, (89 - 110). August 2005. Global Attractivity, Oscillations and Chaos in A Class of Nonlinear, Second Order Difference Equations Hassan Sedaghat Department of Mathematics, Virginia Commonwealth University Richmond, Virginia, 23284-2014, USA hsedagha@vcu.edu ABSTRACT The asymptotic properties of a class of nonlinear second order difference equations are studied. Sufficient conditions that imply the types of behavior mentioned in the title are discussed, in some cases within the context of the macroeconomic business cycle theory. We also discuss less commonly seen types of behavior, such as the equilibrium being simultaneously attracting and unsta- ble, or the occurrence of oscillations away from a unique equilibrium. RESUMEN Se estudian las propiedades asintóticas de una clase de ecuaciones en diferen- cia no lineales de segundo orden. Se discuten condiciones suficientes que implican los tipos de comportamiento mencionados en el t́ıtulo, en algunos casos dentro del contexto de la teoŕıa del ciclo de los negocios macroeconómicos. Además se discuten tipos de comportamiento menos vistos comúnmente, tales como el equilibrio siendo simultáneamente atractivo e inestable, o la ocurrencia de oscila- ciones lejos de un equilibrio único. Key words and phrases: Global attractivity, monotonic convergence, persistent oscillations, absorbing intervals, chaos, off-equilibrium oscillations, unstable global attractors Math. Subj. Class.: 39A10, 39A11. 90 Hassan Sedaghat 7, 2(2005) Introduction Few known difference equations display the wide range of dynamic behaviors that the equation xn+1 = cxn + f (xn − xn−1), 0 ≤ c ≤ 1, n = 0, 1, 2, . . . (1) exhibits with even a limited selection of function types for f (assumed continuous throughout this paper). The nonlinear, second order difference equation (1) has its roots in the early macroeconomic models of the business cycle. Indeed, a version of (1) in which f (t) = αt + β is a linear-affine function first appeared in Samuelson (1939). Various nonlinear versions of (1) subsequently appeared in the works of many other authors, notably in Hicks (1950) and Puu (1993). For more details, some historical remarks and additional references see Sedaghat (2003a). The mapping f in (1) includes as a special case the sigmoid-type map first introduced into business cycle models (in continuous time) in Goodwin (1951). These classical models provide an intuitive context for the interpretation of the many varied results about (1). In this paper we discuss several mathematical results that have been obtained about the asymptotic behavior of (1). These results include sufficient conditions for the global attractivity of the fixed point and conditions that imply the occurrence of persistent oscillations of solutions of (1). Historically, the latter, endogenously driven oscillatory behavior was one of the main attractions of (1) in the economic literature. The case c = 1 which in Puu (1993) models full consumption of savings, is substantially different from 0 ≤ c < 1; we discuss both cases in some detail. We also show that under certain conditions, solutions of (1) exhibit strange and complex behavior. These conditions include a case where the fixed point is globally attracting yet unstable. Also seen as possible is the occurrence of persistent, off- equilibrium oscillations; i.e., oscillations which do not occur about a fixed point. We also state various conjectures and open problems pertaining to (1). The essential background required for understanding the results of this paper is minimal beyond elementary real analysis and some mathematical maturity. However, some readers may benefit from a look at helpful existing texts and monographs such as Elaydi (1999), Kocic and Ladas (1993), LaSalle (1986), Sedaghat (2003a). 1 Oscillations In this first section of the paper, we consider the problem of oscillations for solutions of (1). In addition to being of interest mathematically, from a historical point of view this was the main attraction of business cycle models based on (1). In fact, in those economic models the kind of non-decaying, nonlinear oscillation that is discussed next was of particular interest. 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 91 1.1 Persistent oscillations Consider the general n-th order autonomous difference equation xn+1 = F (xn, xn−1, . . . , xn−m+1) (2) This clearly includes (1) as a special case with m = 2. Definition 1. (Persistent oscillations) A bounded solution {xn} of (2) is said to be persistently oscillating if the set of limit points of the sequence {xn} has two or more elements. Persistent oscillations are basically a nonlinear phenomenon because nonlinearity is essential for the occurrence of robust or structurally stable persistent oscillations. Indeed, if F is linear then its persistently oscillating solutions can occur only when a root of its characteristic polynomial has magnitude one; i.e., for linear maps persistent oscillations do not occur in a structurally stable fashion. Next we quote a fundamental result on persistent oscillations; for a proof which uses standard tools such as the implicit function theorem and the Hartman-Grobman theorem, see Sedaghat (2003a). Theorem 1. Assume that F in Eq.(2) satisfies the following conditions: (a) The equation F (x, . . . , x) = x has a finite number of real solutions x̄1 < . . . < x̄k; (b) For i = 1, . . . , m, the partial derivatives ∂Fi . = ∂F/∂xi exist continuously at X̄j = (x̄j , . . . , x̄j ), and every root of the characteristic polynomial λm − m∑ i=1 ∂Fi(X̄j )λ m−i has modulus greater than 1 for each j = 1, . . . , k; (c) For every j = 1, . . . , k, F (x̄j , . . . , x̄j , x) 6= x̄j if x 6= x̄j . Then all bounded solutions of (2) except the trivial solutions x̄j , j = 1, . . . , k, oscillate persistently. If only (a) and (b) hold, then all bounded solutions that do not converge to some x̄j in a finite number of steps oscillate persistently. The next result is the second-order (and sharper) version of Theorem 1. Corollary 1. Consider Eq.(2) with m = 2 and F = F (x, y). Assume that the following conditions hold : (a) The equation F (x, x) = x has a finite number of solutions x̄1 < . . . < x̄k; (b) Fx = ∂F/∂x and Fy = ∂F/∂y both exist continuously at (x̄j , x̄j ) for all j = 1, . . . , k, with: |Fy(x̄j , x̄j )| > 1 , |Fy(x̄j , x̄j ) − 1| > |Fx(x̄j , x̄j )| . (c) For every j = 1, . . . , k, F (x̄j , y) 6= x̄j if y 6= x̄j . Then all non-trivial bounded solutions oscillate persistently. Definition 2. (Absorbing intervals) Equation (2) has an absorbing interval [a, b] if for every set x0, x−1, . . . x−m+1 of initial values, the corresponding solution {xn} is 92 Hassan Sedaghat 7, 2(2005) eventually in [a, b]; that is, there is a positive integer N = N (x0, . . . x−m+1) such that xn ∈ [a, b] for all n ≥ N. We may also say that F (or its standard vectorization) has an absorbing interval. In the special case where a > 0, (2) is said to be permanent. Remarks. 1. If F in (2) is bounded, then obviously (2) has an absorbing interval. Also, if (2) has an absorbing interval, then obviously every solution of (2) is bounded. The converses of these statements are false; the simplest counter-examples are pro- vided by linear maps which are typically unbounded. A straightforward consideration of eigenvalues shows that if F is linear, then an absorbing interval exists if and only if the origin is attracting. On the other hand, if all eigenvalues have magnitude at most one with at least one eigenvalue having magnitude one, then every solution is bounded although there can be no absorbing intervals. An example of a nonlinear mapping that has no absorbing intervals, yet all of its solutions are bounded is the well-known Lyness map F (x, y) = (a + x)/y, a > 0; also see Theorem 6 below. 2. An absorbing interval need not be invariant, as trajectories may leave it and then re-enter it (to eventually remain there); see Corollary 6 below and the Remark following it. Also an invariant interval may not be absorbing since some trajectories may never reach it. 3. The importance of the concept of permanence in population biology (commonly referred to as “persistence” there) has led to a relatively larger body of results than is available for absorbing intervals in general. These results are also of interest in social science models where the state variable is often required to be positive and in some cases, also bounded away from zero. See Kocic and Ladas (1993) and Sedaghat (2003a) for more examples and details. Our next result requires the following lemma which we quote from Sedaghat (1997). Lemma 1 refers to the first order equation vn+1 = f (vn), v1 = x1 − x0 (3) which with the given initial value relates naturally to (1). Lemma 1. Let f be non-decreasing. (a) If {xn} is a non-negative solution of (1), then xn ≤ cn−1x0 + n∑ k=1 cn−kvk for all n, where {vn} is a solution of (3). (b) If {xn} is a non-positive solution of (1), then xn ≥ cn−1x0 + n∑ k=1 cn−kvk . Theorem 2. Let f be non-decreasing and bounded from below on R, and let c < 1. If there exists α ∈ (0, 1) and u0 > 0 such that f (u) ≤ αu for all u ≥ u0, then (1) has a nontrivial absorbing interval. In particular, every solution of (1) is bounded. 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 93 Proof. If we define wn . = f (xn − xn−1) for n ≥ 1, then it follows inductively from (1) that xn = c n−1x1 + c n−2w1 + . . . + cwn−2 + wn−1. (4) for n ≥ 2. Let L0 be a lower bound for f (u), and without loss of generality assume that L0 ≤ 0. As wk ≥ L0 for all k, we conclude from (4) that xn ≥ cn−1x1 + ( 1 − cn−1 1 − c ) L0 for all n, and therefore, {xn} is bounded from below. In fact, it is clear that there is a positive integer n0 such that for all n ≥ n0, xn ≥ L . = L0 1 − c − 1. We now show that {xn} is bounded from above as well. Define zn . = xn+n0 − L for all n ≥ 0, so that zn ≥ 0 for all n. Now for each n ≥ 1 we note that zn+1 = cxn+n0 + f (xn+n0 − xn+n0−1) − L = czn + f (zn − zn−1) − L(1 − c) . Define g(u) . = f (u) − L(1 − c), and let δ ∈ (α, 1). It is readily verified that g(u) ≤ δu for all u ≥ u1 where u1 . = max { u0, −L(1 − c) δ − α } . If {rn} is a solution of the first order problem rn+1 = g(rn) , r1 = z1 − z0 then since f is bounded from below by L0 − (1 − c)L = 1 − c, we have rn = g(rn−1) ≥ 1 − c for all n ≥ 2. Thus {rn} is bounded from below. Also, if rk ≥ u1 for some k ≥ 1, then rk+1 = g(rk) ≤ δrk < rk . If rk+1 ≥ u1 also, then δrk ≥ rk+1 ≥ u1 and since g is non-decreasing, rk+2 = g(rk+1) ≤ g(δrk) ≤ δ2rk . It follows inductively that rk+l ≤ δlrk as long as rk+l ≥ u1. Clearly there is m ≥ k such that rm < u1. Then rm+1 = g(rm) ≤ g(u1) ≤ δu1 < u1 94 Hassan Sedaghat 7, 2(2005) by the definition of u1. By induction rn < u1 for all n ≥ m. Now Lemma 1(a) implies that for all such n, zn ≤ cn−1z0 + cn−1r1 + · · · + cn−m+1rm−1 + ∑n k=m c n−krk < cn−m+1(z0cm−2 + · · · + rm−1) + u1 ∑n−m k=0 c k = cn−m+1K0 + u1(1 − c)−1(1 − cn−m+1) . Thus there exists n1 ≥ m such that zn ≤ u1 1 − c + 1 for all n ≥ n1. Hence, for all n ≥ n0 + n1 we have xn ∈ [L, M ] where M . = u1 1 − c + 1 − L . It follows that [L, M ] is an absorbing interval. There is also the following more recent result which we quote from Kent and Sedaghat (2003). In contrast to Theorem 1, f is not assumed to be increasing in the next theorem, and if f is unbounded from below then it is also unbounded from above. Theorem 3. Let c < 1 and assume that constants 0 ≤ a < 1 and b > 0 exist such that a 6= (1 − √ 1 − c)2 and |f (t) − at| ≤ b for all t. Then (1) has a non-trivial absorbing interval. In particular, all solutions of (1) are bounded. Remark. It is noteworthy that both Theorems 2 and 3 exclude non-increasing func- tions, except when f is bounded (at least from above). This is not a coincidence; for example, if f (t) = −at then (1) is linear and all solutions are unbounded if c + 1 2 < a < 1. The next corollary concerns the persistent oscillations of trajectories of (1). Corollary 2. In addition to the conditions stated in either Theorem 2 or Theorem 3, assume that f is continuously differentiable at the origin with f ′(0) > 1. Then for all initial values x0, x−1 that are not both equal to the fixed point x̄ = f (0)/(1 − c), the corresponding solution of (1) oscillates persistently, eventually in an absorbing interval [L, M ]. Proof. To verify condition (b) in Corollary 1, we note that Fx(x̄, x̄) = c + f ′(0), Fy(x̄, x̄) = −f ′(0) which together with the fact that f ′(0) > 1 > c imply the inequalities in (b). 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 95 As for condition (c) in Corollary 1, since f is strictly increasing in a neighborhood of 0, if there is y such that x̄ = F (x̄, y) = cx̄ + f (x̄ − y) then f (0) = f (x̄ − y), so that x̄ − y = 0, as required. We now consider an application to the Goodwin-Hicks model of the business cy- cle. This model is represented by the following generalization of Samuelson’s linear equation Yn = cYn−1 + I(Yn−1 − Yn−2) + A0 + C0 + G0 (5) where I : R → R is a non-decreasing induced investment function. The terms Yn give the output (GDP or national income) in period n and the constants A0, C0, G0 are, respectively, the autonomous investment, the minimum consumption and government input. We assume in the sequel that A0 + C0 + G0 ≥ 0. The number c here is the “marginal propensity to consume” or MPC. It gives the fraction of output that is consumed in the current period. If we define the function f (t) . = I(t) + A0 + C0 + G0, t ∈ R, we see that (5) is a special case of (1). The next definition gives more precise infor- mation about that function. Definition 3. A Goodwin investment function is a mapping G ∈ C1(R) that satisfies the following conditions: (i) G(0) = 0 and G(t) + A0 + C0 + G0 ≥ 0 for all t ∈ R; (ii) G′(t) ≥ 0 for all t ∈ R and G′(0) > 0; (iii) There are constants t0 > 0, 0 < a < 1 such that G(t) ≤ at for all t ≥ t0. The next result is an immediate consequence of Corollary 2. It gives specific criteria for persistent oscillations of output trajectories, as is expected of a business cycle. Corollary 3. (Persistent oscillations) Consider the equation yn = cyn−1 + G(yn−1 − yn−2) + A0 + C0 + G0, 0 ≤ c < 1, (6) where G is a Goodwin investment function. If G′(0) > 1, then all non-trivial solutions of (6) oscillate persistently, eventually in the absorbing interval [L, t1/(1 − c) + 1], where t1 ≥ t0 is large enough that G(t) + A0 + C0 + G0 ≤ at for t ≥ t1 if G(t) ≤ at for t ≥ t0 and where L = lim t→−∞ G(t) + A0 + C0 + G0 ≥ 0. 96 Hassan Sedaghat 7, 2(2005) 1.2 Other oscillatory behavior Here we approach the oscillation problem for (1) at a more general level, without requiring that the oscillatory behavior to be persistent. We begin with the following lemma; it gives conditions that imply a more familiar type of oscillatory behavior than that seen in the preceding sub-section. Note that if tf (t) ≥ 0 for all t, then by continuity f (0) = 0 and the origin is the unique equilibrium of (1). Lemma 2. If tf (t) ≥ 0 for all t then every eventually non-negative and every eventually non-positive solution of (1) is eventually monotonic. Proof. Suppose that {xn} is a solution of (1) that is eventually non-negative, i.e., there is k > 0 such that xn ≥ 0 for all n ≥ k. Either xn ≥ xn−1 for all n > k in which case {xn} is eventually monotonic, or there is n > k such that xn ≤ xn−1. In the latter case, xn+1 = cxn + f (xn − xn−1) ≤ cxn ≤ xn so that by induction, {xn} is eventually non-increasing, hence monotonic. The argu- ment for an eventually non-positive solution is similar and omitted. The preceding lemma and the first part of the next theorem are taken from Sedaghat (2003b). Theorem 4. Let 0 ≤ c < 1. (a) If tf (t) ≥ 0 for all t, then (1) has no solutions that are eventually periodic with period two. (b) Let b = ( 1 − √ 1 − c )2 . If β ≥ α > b and α|t| ≤ |f (t)| ≤ β|t| for all t, then every solution of (1) oscillates about the origin. Proof. Let {xn} be a solution of (1). We claim that if c > 0 then for all k ≥ 1, xk > 0 > xk+1 implies xk+2 < 0 xk < 0 < xk+1 implies xk+2 > 0 For suppose that xk > 0 > xk+1 for some k ≥ 1. Then xk+2 = cxk+1 + f (xk+1 − xk) ≤ xk+1 < 0. The argument for the other case is similar and omitted. Now by Lemma 2, if a solution {xn} eventually has period 2, then for all sufficiently large n, there is xn > 0, xn+1 ≤ 0 and xn+2 = xn > 0. If c > 0 then this contradicts the above claim. If c = 0 then 0 < xn = xn+2 ≤ f (xn+1 − xn) ≤ 0 which is again a contradiction. Hence, no solution of (1) can eventually have period two. (b) See Kent and Sedaghat (2003) for a proof. 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 97 2 The Case c=1 We now consider the case c = 1. This case is substantially different from the case 0 ≤ c < 1 and it is informative to contrast these two cases. Also Puu’s equation below reduces to this case. First, we note that with c = 1, Eq.(1) may be put in the form xn+1 − xn = f (xn − xn−1) (7) From this it is evident that the standard vectorization of (7) is semiconjugate to the real factor f relative to the link map H(x, y) . = x − y; see Sedaghat (2003a). Further, the solutions {xn} of (1) are none other than the sequences of partial sums of solutions {vn} of (3), since the difference sequence {∆xn} satisfies (3). Theorem 5. Let {xn} be a solution of the second order equation (7) and let {vn} be the corresponding solution of the first order equation (3). (a) If v∗ is a fixed point of (3) then xn = x0 + v∗n is a solution of (7). (b) If {v1, . . . , vp} is a periodic solution of (3) with period p, then xn = x0 − ωn + vn (8) is a solution of (7) with v = p−1 ∑p i=1 vi the average solution, and ωn = vρn − ρn∑ j=0 vj , (v0 . = 0) where ρn is the remainder resulting from the division of n by p. The sequence {ωn} is periodic with period at most p. Proof. Part (a) follows immediately from the identity xn = x0 + n∑ i=1 vi (9) which also establishes the fact that solutions of the second order equation are essen- tially the partial sums of solutions of the first order equation. To prove (b), observe that in (9), after every p iterations we add a fixed sum∑p i=1 vi to the previous total. Therefore, since n may generally take on any one of the values pk + ρn, where 0 ≤ ρn ≤ p − 1, we have xn = x0 + k p∑ i=1 vi + ρn∑ j=0 vj . (10) Now substituting k = n/p − ρn/p in (10) and rearranging terms we obtain (8). Also ωn is periodic since ρn is periodic, and the period of ωn cannot exceed p, since ωpk = 0 for each non-negative integer k. Corollary 4. If {vn} is periodic with period p ≥ 1, then the sequence {xn − vn} is also periodic with period at most p. In particular, {xn} is periodic (hence bounded) if and only if v = 0. 98 Hassan Sedaghat 7, 2(2005) The next result in particular shows that unlike the case c < 1, under conditions implying boundedness of all solutions, (1) typically does not have an absorbing inter- val. Theorem 6. Assume that there exists a constant α ∈ (0, 1) such that |f (u)| ≤ α |u| for all u. Then every {vn} converges to zero and every {xn} is bounded and converges to a real number that is determined by the initial conditions x0, x1. Proof. Note that |vn+1| = |f (vn)| ≤ α |vn| for all n ≥ 1. It follows inductively that |vn| ≤ αn |v1|, and hence, n∑ k=1 |vk| ≤ |v1| n∑ k=1 αk ≤ α |v1| 1 − α which implies that the series ∑∞ n=1 |vn| converges. It follows at once that {vn} must converge to zero and that {xn} is bounded and in fact converges to the real number x0 + ∑∞ n=1 vn. 3 Complex Behavior Under the conditions of Corollary 3, the unique equilibrium x̄ = A0 + C0 + G0 1 − c of (6) is repelling (or expanding) but it is not a snap-back repeller (see Marotto, 1978 or Sedaghat, 2003a for a definition). This is due to Condition (c) in Corollary 1. Indeed, with a Goodwin function numerical simulations tend to generate quasi- periodic rather than chaotic trajectories. However, if we do not assume that f is increasing, more varied and complex types of behavior are possible. This is the case in Puu’s model, which we describe next. 3.1 Chaos and Puu’s model The number s = 1 − c ∈ (0, 1] is called the marginal propensity to save, or MPS for short. In each period n, a percentage of income sYn is saved in the Samuelson-Hicks- Goodwin models and is never consumed in future periods - hence, savings are said to be “eternal.” At the opposite extreme, we have the case where the savings of a given period are consumed entirely within the next period (Puu, 1993, Chapter 6). Puu suggested an investment function in the form of a cubic polynomial Q seen in the following type of difference equation yn = (1 − s)yn−1 + syn−2 + Q(yn−1 − yn−2) (11) where Q is the cubic polynomial Q(t) . = at(1 − bt − t2), b > 0, a > s. Puu took b = 0 (which makes Q symmetric with respect to the origin); but as we will see later, this 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 99 restriction is problematic (see the remarks on growth and viability below). Equation (11) may alternatively be written as follows yn = yn−1 + P (yn−1 − yn−2) (12) in which we call the (still cubic) function P (t) . = Q(t) − st = t(a − s − abt − at2) Puu’s (asymmetric) investment function. Note that (12) is of the form (1) with c = 1 as in the preceding section. Therefore, each solution {yn} of (12) is expressible as the series yn = y0 + ∑n−1 k=0 zk where {zn} is a solution of the first order initial value problem zn = P (zn−1), z0 . = y1 − y0. (13) Each term zn is just the forward difference yn+1 − yn, and a solution of (13) gives the sequence of output or income differences for (12). In order to study the dynamics of Equations (12) and (13), we gather some basic information about P. Using elementary calculus, it is easily found that the real function P has two critical points ξ± = 1 3 [ −b ± √ b2 + 3 ( 1 − s a )] with ξ− < 0 < ξ+. Similarly, P has three zeros, one at the origin and two more given by ζ± = 1 2 [ −b ± √ b2 + 4 ( 1 − s a )] . Further, if a > s + 1, then for all b > 0, P has three fixed points, one at the origin and two more given by t± = 1 2 [ −b ± √ b2 + 4 ( 1 − s + 1 a )] . Remarks. (Growth and Viability Criteria) Assume that the following inequalities hold: 0 < P 2(ξ−) ≤ P (ξ+). (14) Then it is not hard to see that P (ξ−) < ζ− and that the interval I . = [P (ξ−), max{ζ+, P (ξ+)}] is invariant under P . We refer to inequalities (14) as the viability criteria for Puu’s model as they prevent undesirable outcomes such as negative income. See Figure 1. Next, suppose that P (ξ+) ≤ ζ+, or equivalently, P 2(ξ+) ≥ 0. (15) 100 Hassan Sedaghat 7, 2(2005) Figure 1: A viable Puu investment function In this case, the right half I+ . = [0, ζ+] of I is invariant under P , and it follows that the income sequence {yn} is eventually increasing. For this reason, we refer to condition (15) as the steady growth condition. The function depicted in Figure 1 satisfies both the steady growth and the viability criteria. The proofs of (a) and (b) in the next corollary follow from Theorem 5. For a proof of the rest and some examples, see Sedaghat (2003a). Corollary 5. (Steady growth) Assume that inequalities (14) and (15) hold. Also suppose that a > s + 1 and y0 − y−1 ∈ I+. Then the following statements are true: (a) If P ′(t+) < 1, then each non-constant solution {yn} of (12) is increasing and the difference |yn − t+n| approaches a constant as n → ∞. (b) If P ′(t+) > 1 and {v1, . . . , vk} is a limit cycle of (13), then each non-constant solution {yn} of (12) is increasing and the difference |yn − v̄n| approaches a periodic sequence {ωn} of period at most k, where v̄ . = 1 k k∑ i=1 vi, ωn . = α + v̄ρn − ρn∑ i=0 vi, (v0 . = 0) with α a constant, and ρn the remainder resulting from the division of n by k. (c) If P has a snap-back repeller (e.g., if it has a 3-cycle) then each non-constant solution {yn} of (12) is increasing, the corresponding difference sequence {∆yn} is bounded, and for an uncountable set of initial values, chaotic. 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 101 Remarks. 1. The preceding result shows that unlike the Hicks-Goodwin model, Puu’s model (and hence, (1) with c = 1) is capable of generating endogenous growth (i.e., without external input). Under the conditions of Corollary 5(c), this growth occurs at an unpredictable rate. The implication that the existence of a 3-cycle implies chaotic behavior was first established in the well-known paper Li and Yorke (1975). The existence of 3-cycles implies the existence of snap-back repellers (Marotto, 1978). Figure 2 shows a situation where the fixed point is a snap-back repeller because it is unstable yet a nearby point t0 moves into it. Figure 2: A snap-back repeller in Puu’s investment Chaotic behavior may be observed in the output trajectory {yn} itself and not just in its rate sequence. For instance, if inequalities (14) hold but (15) does not, then I is invariant but not I+. Hence, ∆yn is negative (and positive) infinitely often, and sustained growth for {yn} either does not occur, or if it occurs over longer stretches of time, it will not be steady or strict. See Sedaghat (2003a) for an example of this situation. 3.2 Strange behavior Going in a different direction, note that by (i) and (ii) in Definition 3 a Goodwin function can exist only if A0 + C0 + G0 > 0. To study the consequences of the equality A0 + C0 + G0 = 0, we replace (ii) in Definition 3 by: (ii)′ H is non-decreasing everywhere on R, and it is strictly increasing on an interval (0, δ) for some δ > 0; Here we are using H rather than G to denote the more general type of invest- ment function that (ii)′ allows. The next corollary identifies an important difference between the smooth and non-smooth cases. 102 Hassan Sedaghat 7, 2(2005) Corollary 6. (Economic ruin) Assume that A0 + C0 + G0 = 0. Then every solution of yn = cyn−1 + H(yn−1 − yn−2) (16) converges to zero, eventually monotonically. Moreover, the following is true: (a) If H ∈ C1(R), then H′(0) = 0 and the origin is locally asymptotically stable. Thus, the income trajectory stays near the origin if the initial income difference is sufficiently small. (b) If H(t) = bt on an interval (0, r) for some r > 0 and b ≥ ( 1 + √ 1 − c )2 (17) then the origin is not stable. If 0 = y−1 < y0 < r then the income trajectory {yn} is increasing, moving away from the origin until yn − yn−1 > r, no matter how close y0 is to zero. Proof. If A0 + C0 + G0 = 0, then H(t) = 0 for t ≤ 0. Now, there are two possible cases: (I) Some solution {yn} of (16) is strictly increasing as n → ∞, or (II) For every solution there is k ≥ 1 such that yk−1 ≥ yk. Case (I) cannot occur for positive solutions, since by Theorem 2 the increasing trajectory has a bounded limit ỹ with ỹ = lim n→∞ [cyn−1 + H(yn−1 − yn−2)] = cỹ + H(0) = cỹ, which implies that ỹ = 0. For y−1, y0 < 0 the sequence {yn} is increasing since yn+1 = cyn + H(yn−1 − yn−2) ≥ cyn > yn as long as yn remains negative. Thus either yn → 0 as n → ∞, or yn must become positive, in which case the preceding argument applies. In case (II), we find that yk+1 = cyk < yk so that, proceeding inductively, {yn} is strictly decreasing for n ≥ k. Since the origin is the only fixed point of (16), it follows that yn → 0 as n → ∞. Next, suppose that (a) holds. If H(t) is constant for t ≤ 0, then H′(t) = 0 for t < 0, and thus, H′(0) = 0 if H′ is continuous. Thus the linearization of (16) at the origin has eigenvalues 0 and c, both with magnitude less than 1. Now assume that (b) is true. On the interval (0, r), a little algebraic manipulation shows that due to condition (17), the eigenvalues λ1 and λ2 of the linear equation yn+1 = cyn + b(yn − yn−1) = (b + c)yn − byn−1 (18) are real and that 0 < λ1 = b + c − √ (b + c)2 − 4b 2 < 1 < λ2 = b + c + √ (b + c)2 − 4b 2 . 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 103 With initial values y−1 = 0 and y0 ∈ (0, r), the corresponding solution of the linear equation (18) is yn = y0√ (b + c)2 − 4b ( λn+12 − λ n+1 1 ) which is clearly increasing exponentially away from the origin, at least until yn (hence also the difference yn −yn−1 since y0 −y−1 = y0) exceeds r and H assumes a possibly different form. The instability of the origin is now clear. Remark. (Unstable global attractors) Under conditions of Corollary 6(b), the origin is evidently a globally attracting equilibrium which however, is not stable. This is a consequence of the non-smoothness of the Hicks-Goodwin map at the origin, since in Part (a), where the map H is smooth, the origin is indeed stable. Remark. (Off-equilibrium oscillations) Note that the mapping H(t) of Corollary 6(b) has its minimum value at the origin, which is also the unique fixed point or equilibrium of the system. If the mapping f in (1) is characterized by this property, then solutions of (1) are in general capable of exhibiting other types of strange behavior that do not occur with non-decreasing maps of type H. Suppose that f has a global (though not necessarily unique) minimum at the origin and without loss of generality, assume that f (0) = 0. Then the origin is the unique fixed point of (1). Clearly, if (1) exhibits oscillatory behavior in this case, then such oscillations occur off-equilibrium, i.e., they do not occur about the equilibrium or fixed point. In particular, if xn is a solution exhibiting such oscillations, then its limit superior is distinct from its limit inferior. As a very simple example of this sort of oscillation, it is easy to verify that with f (t) = min{|t|, 1}, c = 0 (1) has a periodic solution {0, 1, 1} exhibiting off-equilibrium oscillations with limit superior 1 and limit inferior 0. However, off-equilibrium oscillations can generally be quite complicated (and include chaotic behavior) with non-monotonic f ; see the example of non-monotonic convergence after Conjecture 1 below. For examples not involving convergence see Sedaghat (2003a). 4 Global Attractivity In this section we consider various conditions that imply the global attractivity of the unique fixed point of (1), namely, x̄ = f (0)/(1 − c). Throughout this section it is assumed that 0 ≤ c < 1. We begin with a condition on f under which the origin is globally asymptotically stable. We need a result from Sedaghat (1998) which we quote here as a lemma. Lemma 3. Let g : Rm → R be continuous and let x̄ be an isolated fixed point of xn+1 = g(xn, xn−1, . . . , xn−m). 104 Hassan Sedaghat 7, 2(2005) Also, assume that for some α ∈ (0, 1) the set Aα = {(u1, . . . , um) : |g(u1, . . . , um) − x̄| ≤ α max{|u1 − x̄|, . . . , |um − x̄|} has a nonempty interior (i.e., g is not very steep near x̄) and let r be the largest positive number such that [x̄−r, x̄ + r]m ⊂ Aα. Then x̄ is exponentially stable relative to the interval [x̄ − r, x̄ + r]. The function g in Lemma 3 is said to be a weak contraction on the set Aα; see Sedaghat (2003a) for further details about weak contractions and weak expansions. As a corollary to Lemma 3 we have the following simple, yet general fact about equation (1). Theorem 7. If |f (t)| ≤ a|t| for all t and 0 < a < (1−c)/2 then the origin is globally attracting in (1). Proof. The inequality involving f in particular implies that f (0) = 0, so that the origin is the unique fixed point of (1). Define g(x, y) = cx + f (x − y) and notice that |g(x, y)| ≤ c|x| + a|x − y| ≤ (c + a)|x| + a|y| ≤ (c + 2a) max{|x|, |y|}. Since c + 2a < 1 by assumption, it follows that g is a weak contraction on the entire plane and therefore, Lemma 3 implies that the origin is globally attracting (in fact, exponentially stable) in (1). Remark. If f (0) = 0 and f is continuously differentiable with derivative bounded in magnitude by a or more generally, if f satisfies the Lipschitz inequality |f (t) − f (s)| ≤ a|t − s| then in particular (with s = 0), |f (t)| ≤ a|t| for all t. However, if f satisfies the conditions of Theorem 7 then it need not satisfy a Lipschitz inequality. Theorems 8 and 9 below improve the range of values for a in Theorem 7 with the help of extra hypotheses. 4.1 When f is minimized at the origin In this sub-section we look at the case where f has a global minimum (not necessarily unique) at the origin. These types of maps were noted in the previous section when remarking on off-equilibrium oscillations. It will not be any loss of generality to assume that f (0) = 0 in the sequel, so that x̄ = 0. This will simplify the notation. We begin with a simple result about the non-positive solutions. Lemma 4. If f (t) ≥ 0 for all t and f (0) = 0 then every non-positive solution of (1) is nondecreasing and converges to zero. Given Lemma 4 and the fact that if xk > 0 for some k ≥ 0 then xn > 0 for all n ≥ k, it is necessary to consider only the positive solutions. Before stating the main 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 105 result of this section, we need another version of Lemma 3 above which we quote here as a lemma. See Sedaghat (1998) or Sedaghat (2003a) for a proof. Lemma 5. Let g : Rm → R be continuous and let x̄ be an isolated fixed point of xn+1 = g(xn, xn−1, . . . , xn−m). Let Vg(u1, . . . , um) = (g(u1, . . . , um), u1, . . . , um−1) and for α ∈ (0, 1) define the set Aα = {(u1, . . . , um) : |g(u1, . . . , um) − x̄| ≤ α max{|u1 − x̄|, . . . , |um − x̄|} If S is a subset of Aα such that Vg(S) ⊂ S and (x̄, . . . , x̄) ∈ S, then (x̄, . . . , x̄) is asymptotically (in fact, exponentially) stable relative to S. The next theorem is from Sedaghat (2003c). Theorem 8. Let 0 ≤ f (t) ≤ a|t| for all t. (a) If a < 1 − c, then every positive solution {xn} of (1) converges to zero. (b) If a < c then every positive solution {xn} of (1) eventually decreases monotoni- cally to zero. (c) If a < max{c, 1 − c} then the origin is globally attracting. Proof. (a) Assume that a < 1 − c. Define g(x, y) = cx + f (x − y) and for x, y ≥ 0 notice that g(x, y) ≤ cx + a|x − y| ≤ cx + a max{x, y} ≤ (c + a) max{x , y}. Since c + a < 1 by assumption, it follows that g is a weak contraction on the non-negative quadrant, i.e., [0, ∞)2 ⊂ Aa+c. Since [0, ∞)2 is invariant under g, Lemma 5 implies that the origin is exponentially stable relative to [0, ∞)2. Thus every positive solution {xn} of (1) converges to zero. (b) Let {xn} be a positive solution of (1). Then the ratios rn = xn xn−1 , n ≥ 0 are well defined and satisfy rn+1 = c + f (xn − xn−1) xn ≤ c + a|xn − xn−1| xn = c + a ∣∣∣∣1 − 1rn ∣∣∣∣ . Since it is also true that rn+1 = c + f (xn − xn−1)/xn ≥ c we have c ≤ rn+1 ≤ c + a ∣∣∣∣1 − 1rn ∣∣∣∣ , n ≥ 0. 106 Hassan Sedaghat 7, 2(2005) If r1 ≤ 1 then since r1 ≥ c, we have c ≤ r2 ≤ c − a + a r1 ≤ c − a + a c < 1 where the last inequality holds because a < c < 1. Inductively, if for k ≥ 2, c ≤ rn < 1, n < k then c ≤ rk ≤ c − a + ac < 1 so that r1 ≤ 1 ⇒ rn < 1 for all n > 1. (19) Now suppose that r1 > 1. Then c ≤ r2 ≤ c + a − a r1 < c + a. If c + a ≤ 1, then r2 < 1 and (19) holds. Assume that a + c > 1 and r2 > 1. Then r3 ≤ c + a − a r2 < r2. The last inequality holds because for every r > 1, c + a − a/r < r if and only if r2 − (c + a)r + a > 0. (20) Inequality (20) is true because the quadratic on its left side can have zeros only for r ≤ 1. Now, if r3 < 1, then (19) holds for n > 2. Otherwise, using (20) we can show inductively that r1 > r2 > r3 > · · · so there is k ≥ 1 such that rk ≤ 1 and (19) applies with n > k. Hence, we have shown that for any choice of r0, the sequence rn is eventually less than 1; i.e., xn < xn−1 for all n sufficiently large and the proof is complete. (c) Immediate from Parts (a) and (b) above and Lemma 4. Figure 3: Global attractivity regions when f is minimized at 0 Figure 3 shows the parts (shaded) of the unit square in the (c, a) parameter space for which global attractivity is established so far.The diagonal lines represent a = 1−c 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 107 and a = c. The horizontal line a = b in the middle of the diagram comes from Sedaghat (2003c) where it is shown that if 1 − b < a, c < b, b = 2/( √ 5 + 1), then the origin is globally asymptotically stable. Numerical simulations indicate that the origin is possibly attracting for points in the unshaded region of Figure 3 also. Therefore, we state the following: Conjecture 1. If 0 ≤ f (t) ≤ a|t| for all t, then the origin is globally attracting for all points of the unit square in the (c, a) parameter space with a, c 6= 1. The next example shows that convergence in Part (a) of Theorem 8 need not be monotonic. Example. Let c < 1/2 and let f (t) = a|t| with c < a < 1 − c. By Theorem 8 every solution {xn} of (1) converges to zero. Let rn be the ratio defined in the proof of Theorem 8(b) and define the mapping φ(r) = c + a ∣∣∣∣1 − 1r ∣∣∣∣ , r > 0. Then rn+1 = φ(rn) for all n ≥ 0 and φ has a unique positive fixed point r̄ = 1 2 [√ (a − c)2 + 4a − (a − c) ] < √ a which is unstable because |φ′(r̄)| = a/ r̄2 > 1. Suppose that r0 < 1, i.e., x0 < x−1 but r0 6= r̄. Then r1 = φ(r0) = φ1(r0) where φ1 is the decreasing function φ1(r) = c − a + a r . Since φ1(r) > 1 for r ∈ (0, r∗) where r∗ = a/(1 + a − c), it follows that either r1 > 1 or some iterate rk = φk1 (r0) > 1. This means that xk > xk−1 while x1 > x2 > · · · > xk−1. Next, rk+1 = φ2(rk) where φ2 is the increasing function φ2(r) = a + c − a r . Since φ2(r) < a + c < 1 for all r we see that rk+1 < 1 and so the preceding process repeats itself ensuring that there are infinitely many terms xkj , j = 1, 2, . . . where the inequality xkj +1 > xkj holds. The magnitude of the up-jump depends on the parameters; since c is the absolute minimum value of φ for r > 0, we see that rn ≤ φ(c) = φ1(c) = a c − (a − c) for all n ≥ 1. Thus xkj < xkj +1 < [ a c − (a − c) ] xkj , j = 1, 2, . . . The difference kj+1−kj need not be a constant function of j. Indeed, if a+c > 1/2, then it can be shown that φ1 has a snap-back repeller at r̄ for a certain range of values of a (see Sedaghat, 2003c). In such a case the ratios rn exhibit chaotic behavior. 108 Hassan Sedaghat 7, 2(2005) 4.2 When tf (t) ≥ 0 The situation we discuss in this sub-section is, in a sense, complementary to the one we considered in the preceding sub-section. However, as seen below there are some interesting parallels between the two cases. The condition tf (t) ≥ 0 encountered in the section Other Oscillatory Behavior above, has significant consequences in the case of convergence too. We note that if tf (t) ≥ 0, then by continuity f (0) = 0 so the origin is the unique fixed point of (1) in this case. The following is proved in Kent and Sedaghat (2003). Theorem 9. (a) Assume that there is a > 0 such that |f (t)| ≤ a|t| and that tf (t) ≥ 0 for all t. If a < 2 − c 3 − c or a ≤ 1 − c then every solution of (1) converges to zero; i.e., the origin is globally attracting. (b) Let b = ( 1 − √ 1 − c )2 . If a ≤ b in Part (a), then every solution of (1) is eventually monotonic and converges to zero. The conditions of Theorem 9 specify the shaded region of the (c, a) parameter space shown in Figure 4 below. Figure 4: Global attractivity regions when tf (t) ≥ 0 The line a = 1 − c and the curve a = (2 − c)/(3 − c) are readily identified (the latter clearly by its intercepts with c = 0 and c = 1). The third curve represents a = b where b is defined in Theorem 9(b). Figure 4 is analogous to Figure 3 and it leads to the following conjecture which is analogous to Conjecture 1. Conjecture 2. If f (t) ≤ a|t| and tf (t) ≥ 0 for all t, then the origin is globally attracting for all points of the unit square(a, c 6= 1) in the (c, a) parameter space. 7, 2(2005) Global Attractivity, Oscillations and Chaos in ... 109 5 Concluding Remarks and Open Problems The preceding sections shed some light on the problem of classifying the solutions of (1). However, there are also many unresolved issues, some of which are listed below as open problems and conjectures (they all refer to the case 0 ≤ c < 1): Conjecture 3. All solutions of (1) are bounded if and only if (1) has an absorbing interval. Problem 1. Find sufficient conditions on f that imply (1) has an absorbing interval when f is minimized at the origin. Conjecture 4. Related to Problem 1 where f (t) ≥ f (0), (1) has an absorbing interval if there is a ∈ (0, 1) and t0 > 0 such that f (t) ≤ a|t| for |t| > t0 Problem 2. Find sufficient conditions on f for the fixed point x̄ = f (0)/(1 − c) to be a snap-back repeller. Together with Theorem 3, this establishes the occurrence of chaotic behavior in a compact set. Conjecture 5. Related to Problem 2, if f (t) is non-decreasing then every solution of (1) is either periodic or almost (or quasi) periodic. Problem 3. Find either sufficient conditions on f, or specify some classes of functions f for which every solution of (1) is eventually periodic or every solution approaches a periodic solution for a range of values of c. Problem 4. Investigate the consequences of f being an even function, i.e., f (−t) = f (t) in the case where f is minimized at zero. Similarly, when tf (t) ≥ 0, what is the significance of the oddness of f (i.e., f (−t) = −f (t)) for the asymptotic behavior of solutions? Problem 5. Extend the results of this paper, where possible, to the more general difference equation xn+1 = cxn + dxn−1 + f (xn − xn−1), c, d ∈ [0, 1]. Puu’s general model is a special case of this equation with c + d ≤ 1. Received: March 2003. Revised: July 2003. References [1] ELAYDI, S.N., An Introduction to Difference Equations, 2nd ed., Springer, New York.(1999). 110 Hassan Sedaghat 7, 2(2005) [2] GOODWIN, R.M., The nonlinear accelerator and the persistence of business cycles, Econometrica, 19(1951), 1-17. [3] HICKS, J.R., A Contribution to the Theory of the Trade Cycle, 2nd ed.(1950), Clarendon Press, Oxford 1965(First ed. Oxford University Press, [4] KENT, C.M. AND H. SEDAGHAT, Boundedness and global attractivity in xn+1 = cxn + f (xn − xn−1), J. Diff. Eq. Appl., to appear. [5] KOCIC, V.L. AND G. LADAS, Global Behavior of Nonlinear Difference Equations of Higher Order with Applications, Kluwer, Dordrecht. (1993). [6] LASALLE, J.P., Stability and Control of Discrete Processes, Springer, New York (1986). [7] LI, T.Y. AND J.A. YORKE, Period three implies chaos, Amer. Math. Monthly 82(1975), 985-992. [8] MAROTTO, F.R., Snap-back repellers imply chaos in Rn, J. Math. Anal. Appl. 63(1978), 199-223. [9] PUU, T., Nonlinear Economic Dynamics, 3rd ed., Springer, New York. (1993). [10] SAMULESON, P.A., Interaction between the multiplier analysis and the principle of acceleration, Rev. Econ. Stat. 21(1939), 75-78. [11] SEDAGHAT, H., A class of nonlinear second order difference equations from macroeconomics, Nonlinear Anal. TMA 29(1997), 593-603. [12] SEDAGHAT, H., Geometric stability conditions for higher order difference equations, J. Math. Anal. Appl. 224(1998), 255-272. [13] SEDAGHAT, H., (2003a) Nonlinear Difference Equations: Theory with Ap- plications to Social Science Models, Kluwer, Dordrecht. [14] SEDAGHAT, H. , (2003b) On the Equation xn+1 = cxn + f (xn − xn−1), Proceedings of the 7th International Conference on Difference Equations and Applications, Changsha, (Changsha, PR China), Fields Institute Com- munications, 42 (2004), 323-326. [15] SEDAGHAT, H., (2003c) The global stability of equilibrium in a nonlinear second order difference equation, International Journal of Pure and Applied Mathematics, 8 (2003), 209-223.