[MUSIC] Okay, now I will give the answer to the previous exercise and this exercise has a special name. It is called, The binomial theorem for negative integer exponents. It is as follows. 1/ (1- q) to the power of k. So 1/ (1- q) to the power of negative k where the name comes from is equal to the following sum for n greater than 0. N + k- 1 choose n times q to the power n. Say for k equal to 1, all these coefficients, Are n choose n, so they're all 1, so we recover our formula for the geometric progression sum. Or for k equal to 2 we recover the previous exercise. And as I said, it is possible to prove this theorem by using the derivation. And this I leave you as an exercise, but we will give a combinatorial proof of that which does not use derivation. So, exercise, Proof, In this theorem, Are using derivation. And since all courses called introduction to integrated combinatorics we'll give the combinatorial proof of this equality. We already know that 1/1- q is 1 + q + q squared + etc. So if we take the kth power of this expression, It is equal to 1 + q + q squared + etc to the power of k, which is equal to the product of k brackets of this form. And this is taken k times. And now suppose we expand this product, And this thing will be just equal to the sum of q to the power d1 + d2 + etc + dk for d1, d2, dk, Arbitrary nonnegative integers. D1, Etc dk greater than or equal to 0. So, this means that we just take a summand d to the power of i, from the ith bracket. And we multiple all the summands and this gives us q to the power d1 + d2 + etc + dk. So we get this sum. Okay, and let us write this as a power series in q. So let us compute the number of ways in which we can get q to the power n here. So this is equal to the sum of q to the power n, Times a certain coefficient. Denoted by a n for n greater than or equal to 0, where, a n is the number of presentations of the number n. As k summands is the number of ways, To present n as d1+ etc + several +dk. The number of presentations n of n as a sum of, k integer nonnegative summands. Okay, and we recall our familiar problem from one of our first lectures. The number of ways to present n as the sum of integer and nonnegative summands is equal to the number of ways to put n balls inside k boxes where the boxes are allowed to remain empty. So this means, well, if we present n in such a way, this corresponds to the following presentation. We put d1 balls into the first box, d2 balls into the second box, etc. And this is a problem we can solve. And the number of such ways is, Nothing but this binomial coefficient. This is n + k -1 choose n, because this is, the balls and boxes construction. So the coefficient in front of q to the power n in this expression equals n + k- 1 choose n. The binomial theorem for negative integer exponents is proved. [MUSIC].