Recurrence equation $g(k+n)=\sum_{j=1}^ng(k+n-j)$ and exponential function

Question

If I have the recurrence equation: $$g(k+n)=\sum_{j=1}^ng(k+n-j)$$ with $g(h)=1$ for $0\le h\lt (n-1)$, is it possible to find a value of $n$ such that: $$\lim_{k\to\infty}\frac{\exp(k)}{g(k)}=0?$$ Thanks.

Answer 1

No, it's not possible. All sequences with a recurrence

$$g(k+n) = \sum_{j=1}^n g(k+n-j)$$

grow slower than $2^k$.

The term of such a sequence is a linear combination of $k^\mu\cdot\xi_\nu^k$, where the $\xi_\nu$ are the zeros of the polynomial

$$X^n - \sum_{j=1}^n X^{n-j},$$

and $\mu$ ranges from $0$ to the multiplicity of the zero $\xi_\nu$ minus one.

Now, if $\xi$ is a root of that polynomial, then $\lvert\xi\rvert \leqslant 1$, or

$$\lvert\xi\rvert^n = \left\lvert\sum_{i=0}^{n-1} \xi^i\right\rvert \leqslant \sum_{i=0}^{n-1} \lvert\xi\rvert^i = \frac{\lvert\xi\rvert^n-1}{\lvert\xi\rvert-1} < \frac{\lvert\xi\rvert^n}{\lvert\xi\rvert-1} \Rightarrow \lvert\xi\rvert < 2.$$

Thus all sequences from which $g(k)$ is combined grow slower than $2^k$, and hence so does $g(k)$.