This post is just to help a friend that wanted to see why

was superpolynomial.

### Getting a simple lower bound

We can start by keeping only the last term. As all the terms are positive, that will give us a lower bound:

.

We can expand the binomial coefficient in terms of factorials

,

and some of the factors inside can then be cancelled with the ones in , leaving the following expression:

.

As we want a lower bound, we can bound the numerator by below and the denominator by above, leaving us a bound without factorials:

.

For any reasonably big value of we will have . If we combine that with factoring out the -1 in the exponent we get

,

removing the problematic floors and arriving to a much simpler expression.

Combining all these bounds we get

,

a much simpler lower bound when compared to the original expression.

### Proving it is superpolynomial

If w take an arbitrary polynomial of degree we can say for that

,

meaning we can bound by above any polynomial of degree by a polynomial of the same degree with a single term.

Taking the limit of the quotient of logarithms,

we can see the lower bound of the original expression is superpolynomial, making the original expression superpolynomial too.