This post is just to help a friend that wanted to see why
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.