Big O Problem

Show that if:

T(1) = a
T(n) = T(n-1) + n^k, for n > 1

then T(n) is O(n^(k+1)).  You may assume k>=0.  Also, show that this is the tightest simple big-oh upper bound, that is, that T(n) is not O(n^m) if m < k+1.  Hint: Expand T(n) in terms of T(n-i), for i = 1,2,..., to get the upper bound.  For the lower bound, show that T(n) is at least cn^(k+1) for some particular c >0.