Binomial theorem for negative integer exponents

Loading...

From the course by National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

51 ratings

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

From the lesson

Generating functions: a unified approach to combinatorial problems. Solving linear recurrences

We introduce the central notion of our course, the notion of a generating function. We start with studying properties of formal power series and then apply the machinery of generating functions to solving linear recurrence relations.

Generating functions: first examples10:40

Formal power series11:54

When are formal power series invertible?9:38

Derivation of formal power series12:31

Binomial theorem for negative integer exponents8:50

Solving the Fibonacci recurrence relation9:29

Solving the Fibonacci recurrence 2: Binet formula6:40

Generating functions of linear recurrence relations are rational7:39

Solving linear recurrence relations: general case10:01

Meet the Instructors

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[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].

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play