06 Dec '02 23:36>
Originally posted by royalchickenThat's not quite what I meant. What I was trying to say was that k(n) = 2n - c -> k(t) =<
given that insight of yours into the don's problem i may be able to solve it
with a generating function. let k(n) be successive coefficients in the
maclaurin series expansion of some continuous differentiable function f(x)...
also, say, as Acolyte did, that for some c, k(n) = 2n - c for all n>=c. note
that n < P(n) <= 2n-c, where P(n) is the s ...[text shortened]... ns.
this is obvious, but having a tight bound on P(n) is knowledge worth having in
the open.
2t - c for all c,n and t >= n. This does indeed give you an upper bound to the solution, but
it's still ~2n for sufficiently large n. What it does show is that none of the terms in the
solution grow or shrink faster than n - ie no n^m, where m>1, and certainly no postive
exponentials. However there could still be terms lurking in there that grow like log n, for
example.
I suspect that the solution will not tend towards a linear equation of the form 2n - c, but
that's just because I know the answer is far from easy to obtain.