Without using any asymptotic bounds for p(n), prove that p(n) grows faster than any polynomial. That is, if f(n) is any polynomial, prove that there is some integer N such that p(n)>f(n) for all n>N.
My teacher started us off by looking at Pk(n), which are the number of partitions of n into k parts. We must show that this is greater than a polynomial of degree k-1. He told us to look at the compositions which is (n-1) choose (k-1). But he said we must divide by something. I'm not really sure how to come up with what we are supposed to divide by or if there is another way to prove this. Any help would be appreciated.