Ponder This Challenge - September 2006 - f(n)=(1+(n*n-n)*f(n-1))/(n*n+1)

Ponder This Challenge:

Puzzle for September 2006.

Let f(n) be a function on the non-negative integers defined recursively as follows:

f(0)=1, f(n)=(1+(n*n-n)*f(n-1))/(n*n+1) for n > 0. So f(1)=1/2, f(2)=2/5 ...

This month's puzzle asks for you to determine the asymptotic behavior of f(n) as n -> infinity. In other words find a simple function g(x) such that f(n)/g(n) -> 1 as n -> infinity.

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

  Answer:

           f(n) is asymptotic to log(n)/n as n -> infinity.
  Here is a proof.  Recall
        f(n) = (1 + (n*n-n)*f(n-1))/(n*n+1)                (1)
  (1) can be rewritten as
        n*f(n) = ((n*n)/(n*n+1))((1/n) + (n-1)*f(n-1))     (2)
  and also as
        (n*n/(n+1))*f(n) = ((n**4)/((n**4)-1))*
        ((n-1)/(n*n)+((n-1)*(n-1)/n)*f(n-1))               (3)
  so if we let
        g1(n)=n*f(n)                                       (4)
        g2(n)=((n*n)/(n+1))*f(n)                           (5)
  (2) and (3) become
        g1(n) = ((n*n)/(n*n+1))((1/n) + g1(n-1)            (6)
        g2(n) = ((n**4)/((n**4)-1))((n-1)/(n*n) + g2(n-1)) (7)
  (6) and (7) imply
        g1(n) < (1/n) + g1(n-1)                            (8)
        g2(n) > (1/n)-(1/(n*n)) + g2(n-1)                  (9)
  applying (8) and (9) recursively
        g1(n) < (1+1/2+ ... +1/n)                          (10)
        g2(n) > (1+1/2+ ... +1/n) -(1+1/4+ ...+1/(n*n))    (11)
  let
        h1(n) = 1 + 1/2 + ... + 1/n                        (12)
        h2(n) = 1 + 1/4 + ... + 1/(n*n)                    (13)
  let c=(pi*pi)/6.  It is well known that h2(n) -> c as n -> infinity.
  Therefore
        h2(n) < c                                          (14)
  so applying (12) and (14) to (10) and (11)
        g1(n) < h1(n)                                      (15)
        g2(n) > h1(n) - c                                  (16)
  using (4) and (5) on (15) and (16)
        f(n) < h1(n)/n                                     (17)
        f(n) > (1/n+1/(n*n))(h1(n)-c)                      (18)
  (18) implies
        f(n) > (h1(n)-c)/n                                 (19)
  it is well known that h1(n) is asymptotic to log(n) as n -> infinity,
  combined with (17) and (19) this implies that f(n) is asymptotic to
  log(n)/n as n -> infinity which is what we wanted to show.

  ---

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

Solvers

• V. Balakrishnan (09.07.2006 @11:58:45 AM EDT)
• Richard Mann (09.07.2006 @04:38:17 PM EDT)
• Arthur Breitman (09.07.2006 @05:15:15 PM EDT)
• Dan Dima (09.07.2006 @07:57:03 PM EDT)
• Oleg Trott (09.08.2006 @01:08:46 AM EDT)
• Michael Quist (09.08.2006 @01:12:09 AM EDT)
• Aravind (09.08.2006 @04:33:53 AM EDT)
• Frank Yang (09.08.2006 @10:42:16 AM EDT)
• Dinesh Krithivasan (09.08.2006 @03:04:21 PM EDT)
• David McQuillan (09.08.2006 @04:32:33 PM EDT)
• Lizhao Zhang (09.08.2006 @09:04:46 PM EDT)
• Alan Murray (09.09.2006 @01:12:40 AM EDT)
• Wolf Mosle (09.09.2006 @01:58:56 PM EDT)
• Jerold Lewandowski (09.09.2006 @05:55:42 PM EDT)
• Didier Bizzarri (09.09.2006 @09:05:37 PM EDT)
• Arjun Acharya (09.10.2006 @02:08:20 PM EDT)
• Zhou Guang (09.10.2006 @10:52:47 PM EDT)
• Vincent Vermaut (09.11.2006 @10:40:49 AM EDT)
• Arvind L. (09.11.2006 @11:32:28 AM EDT)
• Victor Popov (09.11.2006 @05:23:35 PM EDT)
• S. Amghibech (09.11.2006 @08:15:17 PM EDT)
• John Fletcher (09.12.2006 @01:25:22 PM EDT)
• Paolo Massaro (09.12.2006 @03:47:42 PM EDT)
• Emilio Schiavi (09.12.2006 @05:37:41 PM EDT)
• John T. Robinson (09.12.2006 @07:10:07 PM EDT)
• John Ritson (09.13.2006 @04:05:06 AM EDT)
• Piotr Zielinski (09.13.2006 @05:27:54 PM EDT)
• John Dalbec (09.13.2006 @07:50:17 PM EDT)
• Wu Hao (09.13.2006 @09:34:43 PM EDT)
• Luke Pebody (09.14.2006 @05:43:02 AM EDT)
• Matthew Samuel (09.14.2006 @11:45:19 PM EDT)
• Ariel Flat (09.14.2006 @05:40:52 PM EDT)
• Lawrence Hon (09.15.2006 @06:13:17 AM EDT)
• Phil Muhm (09.15.2006 @10:15:57 AM EDT)
• Du Yang (09.17.2006 @02:55:50 AM EDT)
• Se Kwon Kim (09.18.2006 @03:13:23 AM EDT)
• Mingrui Wu (09.18.2006 @08:11:28 AM EDT)
• Steven Noble (09.18.2006 @11:56:28 PM EDT)
• Christian Blatter (09.19.2006 @06:23:03 AM EDT)
• Dion Harmon (09.19.2006 @06:11:14 PM EDT)
• Dave Parashar (09.20.2006 @09:39:11 AM EDT)
• Yoav Raz (09.21.2006 @12:01:06 AM EDT)
• Chris Shannon (09.22.2006 @12:02:17 AM EDT)
• Joachim Ripken (09.22.2006 @07:46:46 AM EDT)
• Oded Margalit (09.23.2006 @04:43:19 PM EDT)
• Anatoly Morosov (09.26.2006 @11:28:21 AM EDT)
• Ray Gregory (09.28.2006 @10:06:13 PM EDT)
• Firat Solgun (09.29.2006 @05:23:02 PM EDT)
• William Hasenplaugh (09.29.2006 @07:20:25 PM EDT)
• Li Han (10.01.2006 @11:39:40 AM EDT)