Subscribe to DSC Newsletter

Challenge of the Week: Interesting Recursive Formula

We ask you to prove the following. If we recursively define S(n) using

S(n+1) = { 1 + R(n) } S(n) - R(n) S(n-1),

with S(1) = p and S(2) = q (arbitrary numbers), and R is an arbitrary function, then S(n) is equal to

S(n) = a(1) + a(2) + ... + a(n)


  • a(n) = a(1) * { R(n-1) * R(n-2) * ... * R(1) }
  • a(1) = p
  • a(2) = q - p

Also, R(n) = a(n+1) / a(n).

For example, if a(n) = (-1)^{n+1} * ( 1/n ), then S(n) = 1 - 1/2 + 1/3 - 1/4.... + (-1)^{n+1} * (1/n), and S(n) tends to log(2) as n tends to infinity. If a(n) = 1/n, then S(n) does not converge, and it is asymptotically equal to log(n).

In which contexts can this formula be useful?

Here we are trying to find some S(n) that very quickly converges to a transcendental number, to develop high quality, random number generators. The example provided here, with S(n) converging to log(2), while converging to a transcendental number, is poor because the convergence is extremely slow. Note that for convergence, R(n) must converge very quickly to -1 or +1. Do you have an idea for a much better example?

For other weekly challenges, click here. For another interesting recursive relation, see my article in Journal of Number Theory. It proves that

The recursive relation g(n) = n − g(g(n − 1)), g(0) = 0, appears in the context of Fibonacci numbers, as you can see in Hofstadter [“Bach, Esher, Godel,” pp. 151–154, Intereditions, 1985]. Here we state and prove that g(n) = [(n+1)(-1 + SRT(5))/2], where [] represents the integer part function.

Views: 1805

Reply to This

Replies to This Discussion

You can prove this with some straightforward algebra. Define a(n) = S(n) - S(n-1) for n>=2. The sum follows immediately, and it's easy to show that a(n+1) = R(n)a(n) by the recursive definition of S(n). This product telescopes back to n=2, though, not n=1. R(n) is not defined for n=1; otherwise, you would have to define S(0).

Reply to Discussion


Follow Us


  • Add Videos
  • View All


© 2017   Data Science Central   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service