Ponder This Challenge - May 2003 - sqrt(1+2*sqrt(1+3*sqrt(...+n*sqrt(1]

Ponder This Challenge:

This month's puzzle was suggested by Venkateshwar Rao Thota, based on a result of Srinivasa Ramanujan.

I will use "sqrt" to denote the positive square root, "b*c" to denote multiplication, and "b**c" to denote exponentiation (b raised to the c power).

Define f(n)=sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(1+5*sqrt(...+n*sqrt(1)...))))) So f(1)=sqrt(1)=1, f(2)=sqrt(1+2)=sqrt(3)=1.732..., f(3)=sqrt(1+2*sqrt(1+3))=sqrt(1+4)=sqrt(5)=2.236... .

Clearly f is an increasing function of n.

First part: Give (with proof) a bound B such that f(n)<B for all n.

Second part: Give (with proof) an integer n such that f(n) > B - 1/10**100, that is, f(n) agrees with B up to 1 in the 100th decimal place.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  B=3.

  3 = sqrt(9)
   = sqrt(1+8)
   = sqrt(1+2*sqrt(16))
   = sqrt(1+2*sqrt(1+15))
   = sqrt(1+2*sqrt(1+3*sqrt(25)))
   = sqrt(1+2*sqrt(1+3*sqrt(1+24)))
   = sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(36))))
   = sqrt(1+2*sqrt(1+3*sqrt(1+4*sqrt(1+35))))

  Stop after n steps to show B>f[n]:
  3 = sqrt(1+2*sqrt(16)) > sqrt(1+2*sqrt(1)) = f[2]
  3 = sqrt(1+2*sqrt(1+3*sqrt(25))) > sqrt(1+2*sqrt(1+3*sqrt(1))) = f[3]

  To show the lower bound, consider a fixed value of n.
  For k between 1 and n, define
  t[k] = k*sqrt(1+(k+1)*sqrt(1+(k+2)*sqrt(...+n*sqrt(1)...)))
  so that t[n]=n,
  t[k]=k*sqrt(1+t[k+1])
  and t[1]=f[n].
  Also define r[k]=t[k]/(k*(k+2)).

  Show inductively that sqrt(r[k+1])<r[k]<1.
  Indeed r[n]=1/(n+2)<1, and we can calculate
  k*(k+2)*r[k]=t[k]=k*sqrt(1+t[k+1])=k*sqrt(1+(k+1)*(k+3)*r[k+1]);
  (k+2)**2 * r[k]**2 = 1 + (k+1)*(k+3)*r[k+1] > (1+(k+1)*(k+3))*r[k+1];
  r[k]**2 > r[k+1],
  and r[k]<1.

  Deduce that
  1 > r[1] > r[n]**(1/2**(n-1)) = 1/(n+2)**(1/2**(n-1))
  0 > log r[1] > - (log(n+2)) / 2**(n-1)  (natural logarithms).
  Setting n=338, we estimate
  log r[1] > - log(340)/2**339 > -1/(3*10**100),
  and f[338]=t[1]=3*(1-r[1])>3-1/10**100, as required.

Solvers

• Joe Fendel (5.01.2003 @03:52:13 PM EDT)
• Rocke Verser (None)
• Oleg Mazurov (5.01.2003 @05:47:02 PM EDT)
• Vitaly Stakhovsky (5.01.2003 @05:47:02 PM EDT)
• Alexey Vorobyov (5.01.2003 @09:02:15 PM EDT)
• Ling Li (5.01.2003 @09:59:53 PM EDT)
• Hagen von Eitzen (5.02.2003 @12:04:34 PM EDT)
• Yunhong Zhou (5.03.2003 @04:09:23 AM EDT)
• Surendar Reddy Nanchary (5.02.2003 @03:47:46 PM EDT)
• Michael Brand (5.04.2003 @06:39:00 AM EDT)
• Klaus Hoffmann (5.03.2003 @03:47:58 PM EDT)
• Gyozo Nagy (5.04.2003 @03:36:10 AM EDT)
• JoséH. Nieto (5.04.2003 @09:50:01 AM EDT)
• Venezuela Maracaibo (5.04.2003 @09:50:01 AM EDT)
• Ignacio Larrosa Cañestro (5.04.2003 @06:14:34 PM EDT)
• Coserea Gheorghe (5.05.2003 @02:56:54 AM EDT)
• George J. Ross (5.05.2003 @10:44:10 AM EDT)
• Paul Lee (5.05.2003 @07:28:35 PM EDT)
• David Woodruff (5.06.2003 @02:26:43 AM EDT)
• Nis Jorgensen (5.06.2003 @04:44:39 AM EDT)
• Abhinav Kumar (5.07.2003 @01:51:39 AM EDT)
• John G. Fletcher (5.07.2003 @08:42:06 PM EDT)
• Ariel Flat (5.08.2003 @01:51:18 PM EDT)
• Alex Proudfoot (5.09.2003 @03:26:29 AM EDT)
• Shmuel Spiegel (5.09.2003 @04:19:06 AM EDT)
• Karl Dsouza (5.11.2003 @01:01:18 AM EDT)
• Amit Sinha (5.12.2003 @03:27:42 AM EDT)
• Andreas Knappe (5.12.2003 @04:45:35 AM EDT)
• Jitesh Jain (None)
• R. Nandakumar (5.20.2003 @08:40:23 AM EDT)
• Raghav Boinepalli (5.21.2003 @02:13:57 PM EDT)
• Daniel Chong Jyh Tar (5.21.2003 @09:41:56 PM EDT)
• Maxim G. Smith (5.22.2003 @03:19:49 PM EDT)
• Dave Blackston (5.23.2003 @01:11:37 PM EDT)
• Wei Liu (5.23.2003 @03:09:13 AM EDT)
• Florbela Duarte (5.26.2003 @07:20:32 PM EDT)
• Vishal Goel (5.30.2003 @01:20:25 AM EDT)
• Alexis G Megas (5.30.2003 @06:22:57 PM EDT)
• Dan Dima (6.1.2003 @05:50:12 AM EDT)
• Dan Yu (6.2.2003 @04:42:50 AM EDT)
• Andre Rzym (6.2.2003 @03:02:13 PM EDT)