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)
where
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.
Tags:
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).
© 2020 TechTarget, Inc. Powered by
Badges | Report an Issue | Privacy Policy | Terms of Service
Most Popular Content on DSC
To not miss this type of content in the future, subscribe to our newsletter.
Other popular resources
Archives: 2008-2014 | 2015-2016 | 2017-2019 | Book 1 | Book 2 | More
Most popular articles