[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1967.0. "Concours General, France, 1995, problem 1" by BATVX1::ESANU (Au temps pour moi) Wed Apr 19 1995 07:54

Study the convergence of the sequence defined by

	u(0) >= 0
	                         1
	u(n+1) = sqrt (u(n)) + -----
	                       n + 1

T.R Title User Personal
Name Date Lines

1967.1 Some results FLOYD::YODER MFY Fri Apr 21 1995 18:25 47

T.R	Title	User	Personal Name	Date	Lines
1967.1	Some results	FLOYD::YODER	MFY	`Fri Apr 21 1995 18:25`	47
	I think it is fairly easy to show that 2 3 (1) u[n] = (1+1/n) + O(1/n ) 2 (2) For n >= 7, u[n] > (1+1/n) (3) For n >= 7, u[n] is monotone decreasing to a limit of 1. Verifying (2) for n = 7 can be done by computer. 2 2 For n > 0, put u[n] = (1+1/n) v[n] where v[n] > 0. We have 1/2 u[n+1] = u[n] + 1/(n+1) = (1+1/n)v[n] + 1/(n+1) 2 2 u[n+1] = ((n+2)/(n+1)) v[n+1] Rearranging terms, 2 3 2 3 2 2 3 2 v[n+1] = v[n](n + 3n + 3n + 1)/(n + 4n + 4n) + (n + n)/(n + 4n + 4n) So by a trivial induction v[n] > 1 for n >= 7, proving (2) above. Showing that u[n] is monotone decreasing can be done by solving a quadratic: if u[n] = u[n+1] and u[n] > 1, we must have (putting x = u[n]) (x - 1/(n+1))^2 = x 2 2 x = b/2 + sqrt(b - 4/(n+1) ) where b = (n+3)/(n+1) x = 1/(2(n+1))*(n+3+sqrt(n^2 + 6n + 5)) 2 x < [same with 9 in place of 5] = (n+3)/(n+1) = 1 + 2/(n+1) < (1 + 1(n+1)) so another induction gives (3). Finally, now that we know u[n] -> 1, we know v[n] -> 1, and from v[n] > 1 we get 2 3 2 3 2 v[n+1] < v[n](n + 4n + 4n + 1)/(n + 4n + 4n) 2 3 or v[n+1] < v[n](1 + O(1/n )) which gives us (1).

I think it is fairly easy to show that

                    2       3
  (1) u[n] = (1+1/n) + O(1/n )
                               2
  (2) For n >= 7, u[n] > (1+1/n)

  (3) For n >= 7, u[n] is monotone decreasing to a limit of 1.

Verifying (2) for n = 7 can be done by computer.
                             2    2
For n > 0, put u[n] = (1+1/n) v[n]  where v[n] > 0.  We have

               1/2
  u[n+1] = u[n]   + 1/(n+1) = (1+1/n)v[n] + 1/(n+1)

                        2      2
  u[n+1] = ((n+2)/(n+1)) v[n+1]

Rearranging terms,
        2         3    2            3    2          2       3    2
  v[n+1]  = v[n](n + 3n + 3n + 1)/(n + 4n + 4n) + (n + n)/(n + 4n + 4n)

So by a trivial induction v[n] > 1 for n >= 7, proving (2) above.

Showing that u[n] is monotone decreasing can be done by solving a quadratic: if
u[n] = u[n+1] and u[n] > 1, we must have (putting x = u[n])

  (x - 1/(n+1))^2 = x
                  2         2
  x = b/2 + sqrt(b - 4/(n+1) )  where b = (n+3)/(n+1)

  x = 1/(2(n+1))*(n+3+sqrt(n^2 + 6n + 5))
                                                                            2
  x < [same with 9 in place of 5] = (n+3)/(n+1) = 1 + 2/(n+1) < (1 + 1(n+1))

so another induction gives (3).

Finally, now that we know u[n] -> 1, we know v[n] -> 1, and from v[n] > 1 we get

        2         3    2            3    2
  v[n+1]  < v[n](n + 4n + 4n + 1)/(n + 4n + 4n)

         2                3
or v[n+1] < v[n](1 + O(1/n ))

which gives us (1).