I am looking at defining a function a(n) in terms of another function f(n), with a(n) defined as:

a(n) = f(n) - ∑

_{i=1}

^{n-1}( f(i)*a(n-i) )

I have noticed that for some functions f, the sum of a(n) over positive integers n goes to 1. I have proved this for f(n)=1/(n+1) , as well as for f(n) = c , where 0<c<1 is constant (the inequalities here are strict.). (I can fetch the proofs of these if desired)

Call the sum of the first n values of a(n), b(n). Call the sum of the first n values if f(n), g(n).

I have noticed that b(n) = g(n) - ∑

_{i=1}

^{n-1}( f(i)*b(n-i) ),

which I thought was interesting, because it has a very similar form to the definition of a(n).

The values of f in the context I am looking at represent probabilities, so they should all be between 0 and 1.

f(n) is, as I am looking at it, the probability that the first n terms of a permutation of the natural numbers is by itself a permutation of the first n natural numbers. a(n) is the probability that this is the case, and that there is no n* < n such that the first n* terms of the permutation is a permutation of the first n* natural numbers.

So, the sum over a(n) should be the probability that there is some N such that the first N terms of the random permutation is a permutation of the first N natural numbers.

There are a few different probability distributions over the permutations of the natural numbers which I am considering, and these give rise to different functions for f. One of the nicest ones I've found has f(n)=1/(n+1) , and as I've mentioned, I've shown that the sum over a(n) in that case does sum to 1. (Well, ok, I've shown it under the assumption that the oeis sequence that came up and the description also made sense as matching what I was doing was the same sequence as what I was looking for. Haven't strictly proven it yet, but I'm fairly sure I'm right about it. Relates to the bernoulli numbers. I can give the argument for this upon request.)

However, another possible distribution which is of interest to me has a much less nice function for f.

What I am hoping is the case is that in the other distribution(s) I am looking at, that the associated f function will give an a(n) function which also sums to 1.

So, I thought that instead of looking at the particular f(n) for that distribution, I would consider how a(n) depends on f(n) in general.

I have found a few things :

f(n) >= (f(1))^n , provided that f(n) always in (0,1) and that a(n) always in [0,1) .

a(n) can be expressed as a sum of all the products of f(m_i) such that the sum of the m_i is equal to n, which corresponds to a partition of n, with coefficients being, assuming I am correct about the oeis sequence being right for this, basically the number of distinct ways to order that particular partition, along with a sign depending on the ways to order that partition or something like that. I don't know what a good notation to use for this sum would be.

Looking experimentally/computationally, a number of the functions I have tried for f(n) (such as 1/sqrt(n+1) ) do seem to make the partial sums of a(n) converge to 1. Some of these however are cases that wouldn't make sense, because they have some negative values for a(n) sometimes, and so it converges to 1 from both sides. I think this sort of thing shouldn't happen with any function f(n) which would actually make sense for my purpose though. I think these functions converging to 1 even in these cases suggests that it might be easier to show that the b(n) -> 1 in a fairly broad range of cases.

Some restrictions on what functions f(n) I think are likely to be relevant:

non-increasing, positive, limit being 0

The oeis sequences which I believe should be the (negative of) the coeffecients for the terms that correspond to the different permutations : http://oeis.org/A111786

If anyone would like to give any feedback or assistance with any of this, I'd appreciate it.

I've been wishing I had someone to work with on my little math projects...