I think the fact that we're counting "how many times k appears" rather than "in how many compositions k appears" helps us out, because it frees us from worrying about duplicate counting.
Consider n=5, k=2.
We want to fix **. There are 4 ways to do this
In red are marked the bars that must be in place in order for the part of size 2 to be intact. The bars in black can be either on or off.
So it can be seen that the count is 2^2 + 2 + 2 + 2^2 = 12, which is correct and matches with the formula given.
I haven't tried to generalize, but if your professor says that it will work out, it probably will. Try it and see what happens.