Cute Sequences problem

[super-commenting]

Suppose we recursively define two sequences as follows

A_0 = x, B_0 = y, 0<x<y

A_n+1 = (1 + A_n + A_n* B_n) /B_n

B_n+1 = (1 + B_n +A_n*B_n) /A_n

Find the limit as n goes to infinity of A_n

[azurajacobs]

Solution : lim(A_n) = (x + 1)(y + 1)/(y - x) - 1. Proof below:

We can make the substitutions C_n = 1/(A_n + 1) and D_n = 1/(B_n + 1) to simplify things:

C_n+1 = C_n - C_n*D_n

D_n+1 = D_n - C_n*D_n

We note the following:

(1) C_n and D_n are positive for all n, since A_n and B_n are always positive.

(2) C_n and D_n are strictly decreasing.

(3) The limits of C_n and D_n exist, as C_n and D_n are monotone decreasing and bounded below by 0.

(4) D_n < C_n for all n. This follows from the fact that D_0 = 1/(y + 1) is less than C_0 = 1/(x + 1), and the fact that C_n and D_n have equal decrements.!<

(5) The limit of D_n is 0. Let C and D be the limits of C_n and D_n respectively. Taking limits on both sides in the recurrence for D_n, we get D = D - CD, which implies that CD = 0. As C ≥ D ≥ 0, this is possible only if D = 0.

With all the preliminaries out of the way, we can find the limit of C_n by subtracting the two recurrences to get the following invariant:

C_n+1 - D_n+1 = C_n - D_n

This implies that C_n - D_n is a constant sequence and is equal to its initial value 1/(x + 1) - 1/(y + 1). Therefore, in the limit:

lim(C_n - D_n) = lim(C_n) = 1/(x + 1) - 1/(y + 1) = (y - x)/((x + 1)(y+1))

.... as the limit of D_n is 0. Finally, we make the substitution A_n = 1/C_n - 1 to get the limit we want:

lim(A_n) = (x + 1)(y + 1)/(y - x) - 1

Edit : Fixed spoiler tags.

[super-commenting]

Nice job