What function is asymptotically eqyivalent to $\sum_{k \geq 0}k!/N^k$?

Question

I am working on this problem to find a function $f(N)$ s.t.

$$ f(N) \sim \sum_{k \geq 0}\frac{k!}{N^k} $$

where $\sim$ means that given functions $f$ and $g$, we have $f \sim g \implies f = O(g) \text{ and } f=\Omega(g)$.

For instance, given the right hand side of the equation above, on input $N$ we have the following (it's a divergent series)

$$ f(N) \sim 1 + \frac{1}{N} + \frac{1}{2N^2} + \frac{1}{6N^3} + O\bigg(\frac{1}{N^4}\bigg) $$

The closest function I can think of are the binomials where:

$$ (N \text{ choose } r) \sim \frac{N^r}{r!} $$

But it doesnt really equal the first equation above. Any help?

Answer 1

Following Robert Israel's suggestion.

Since $(f(x)/x)' = - f(x)/x + 1/x $, if we let $g(x) = f(x)/x$ then $g'+g = 1/x$, $e^x(g'+g) = e^x/x$, $(e^xg)' = e^x/x$, $e^xg = \int e^x/x$, $f(x)/x =g =e^{-x}\int(e^t dt)/t $ so $f(x) =xe^{-x}\int(e^t dt)/t $.

Answer 2

Hint: formally, your divergent series satisfies the differential equation $$ (f(x)/x)' = - f(x)/x + 1/x$$