Chain rule. Inverse function theorem

Loading...

En provenance du cours de National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

63 notes

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

63 notes

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.

À partir de la leçon

Generating functions, continued. Generating function of the Catalan sequence

In this lecture we discuss further properties of formal power series. In particular, we prove an analogue of the binomial theorem for an arbitrary rational exponent. We apply this technique to computing the generating function of the sequence of Catalan numbers.

Composition of formal power series9:14

Derivation and integration of formal power series10:29

Chain rule. Inverse function theorem7:24

Logarithm. Logarithmic derivative5:48

Binomial theorem for arbitrary exponents13:19

Generating function for Catalan numbers14:30

Rencontrer les enseignants

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

From your calculus course,

you know how to compute the derivative of the composition of two functions.

This is done by the chain rule.

Essentially the same rule holds for a formal power series.

Suppose we have two power series A(q).

A0 + a1q + a2q squared plus etc.

And B(q), and

B(q) has no constant term so

it starts with b1q + b2q squared

+ b3q to the 3rd plus etc.

And if you want to compute the derivative of their composition.

So theorem chain

rule says that

A(B(q)) prime

is A prime of B(q)

times B prime of q.

Proof.

And straightforward,

so let's take A(B(q)) prime and

this is the derivative of

anB(q) to the power n.

And the whole thing is linear.

So the derivative operator is linear.

So, this is equal to

anB(q) to the power n prime.

And this thing can be computed by the latence rule.

So, this is, And

greater than or equal to 0, and when you apply

the latence rule to this product, you get,

an, and then you get n times B prime of q,

times B(q) to the power of n- 1.

Because you apply the derivative of the product of n factors and

each of the factors gives you the derivative of each

factor is B prime and the rest is B to the power n- 2.

So in each column you have, B prime of q.

And here you have an times n times

B(q) to the power n- 1.

And B prime of q.

And this is nothing but the derivative of,

The power series A composed with B.

So this is A prime (B(q))

times B prime of q.

The proof is finished.

A very important corollary of this chain rule is the inverse function theorem.

Which is also probably familiar to you from the MLS' course.

So if we have two powers of series

which are inverse to each other,

so if A of B(q), if their composition

is just q then the derivatives

are related as follows.

Then A prime (t) is equal

to 1 over B prime of q,

Where t is

B(q).

The proof is as follows.

Let us take this equality and

compute the derivatives of both sides using the chain rule.

That means that A(B(q))

prime times B prime of q

is q prime, that is 1.

So, A prime of B(q)

is 1 over B prime of q.

So A(t) is 1 over B prime(q) where t is B(q).

The inverse functional theorem is proved.

We'll use the theorem to define logarithm.

[MUSIC]

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play