Sign up ×

Given any computable function $f(x)$, is there an algorithm to find a set of coefficients $a_n$, such that
i) $g(x)=\sum_{n=1}^{n=\infty} a_nx^n$ converges for all $x>1$
ii) $g(x)$ eventually dominates $f(x)$

If not, is there a way to approach this boundary from above or below?

share|cite|improve this question

1 Answer 1

up vote 1 down vote accepted

If you take $f$ to be a computable function from $\Bbb Z_{>0}$ to $\Bbb Z_{>0}$, the answer is yes. Define $h:\Bbb Z_{>0}\to \Bbb Z_{>0}$ recursively by $h(1)=f(1)$, $h(n+1)=\max(f(n+1),h(n)+1)$ if $n\ge 1$. Then $$g(x):=\sum_{n\ge 1} \frac{x^{h(n)}}{n^{h(n)}}(h(n)+1)$$ converges everywhere (by the root test), and for all $m\in \Bbb Z_{>0}$, looking at the $m$th term of the series, $$g(m)\ge h(m)+1>f(m).$$

share|cite|improve this answer

Your Answer


