Bernoulli's Inequality

Loading...

En provenance du cours de University of California San Diego

Mathematical Thinking in Computer Science

286 notes

University of California San Diego

Mathematical Thinking in Computer Science

286 notes

Cours 1 sur 5 dans Specialization Introduction to Discrete Mathematics for Computer Science

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the course, we use a try-this-before-we-explain-everything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

À partir de la leçon

Recursion and Induction

We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to make convincing arguments for arbitrarily large and complex problems by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher's problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Introduction, Lines and Triangles Problem10:16

Lines and Triangles: Proof by Induction5:59

Connecting Points12:59

Odd Points: Proof by Induction5:29

Sums of Numbers8:52

Bernoulli's Inequality8:01

Coins Problem9:45

Cutting a Triangle8:40

Flawed Induction Proofs9:28

Alternating Sum9:09

Rencontrer les enseignants

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Vladimir Podolskii
Associate Professor
Computer Science Department

[MUSIC].

Hi, in this video we will talk about mathematical fact called

Bernoulli's inequality.

Bernoulli is a famous mathematician and this inequality was named after him.

And we're going to use his inequality to solve a practical problem, and

we will prove the inequality itself using mathematical induction.

So the practical problem is, imagine you start with having $1,000,

and you earn 2% of what you have every single day.

Will you ever get more than $1 million?

Well what happens is on day one you have $1,000, and on day two you have 2% more.

So we have $1,000 multiplied by 1.02.

And on day three you have that multiplied once again with 1.02.

So you get 1,000 times 1.02 times 1.02,

which is equal to $1,000 times 1.02 squared.

And repeating this, we get that on day n,

you have 1,000 times 1.02 to the power of n-1.

Now that we know how much you're going to have every single day,

we can reformulate this problem in a mathematical way.

The question now is, is there such integer n that 1,000

times 1.02 to the power of n Is bigger than 1 million.

Or, we can divide by 1,000, the left part and the right part and ask,

is there such n that 1.02 to the power of n is bigger than 1,000.

This is a question because although we get increasing powers of this number,

this number is very close to 1 so it will increase really slowly.

And maybe it won't get bigger than 2 or maybe it won't get bigger than 10.

It is not obvious from the start.

Let's see.

To see about that, we'll use Bernoulli's inequality.

And the theorem states that for any integer n which is greater or

equal to 0, and any positive number x which doesn't have to be integer,

just any positive real number x.

1 + x to the power of n is greater than or equal to 1 + nx.

And first, before using this inequality, we're going to prove it.

And we're going to prove it using mathematical induction, again.

First, we need to proof base and the best case in this case is n = 0,

because we are proving the statement for all non-negative integers, n.

In this case, 1 + x to the power of n is equal to 1 + x to the power of 0.

And any number to the power of 0 is just 1.

And this is equal to 1 + 0 times x, which is equal to 1 + nx.

So in this case we have equality.

We were going to prove inequality but

equality is a particular case, because we needed to prove

that 1 + x to the power of n is greater than or equal to 1 + nx.

And in case n equal 0 it is just equal.

Now, we need to prove also the induction step from n to n + 1.

And we assume that for some n,

we have proven that 1 + x to the power of n is greater than or equal to 1 + nx.

Now, we need to prove for n + 1.

So we will get 1 + x to the power of n + 1, and we separate it into two multiples,

1 + x to the power of n and just 1 + x.

And now, we mark with an exclamation the fact that we're going to

use the assumption of the induction.

And the assumption of the induction is that for n,

we have already proven our theorem.

And we know that 1 + x to the power of n is greater than or equal to 1 + nx.

And we can multiply this inequality by 1 + x.

1 + x is a positive number because 1 is positive and x is positive.

So, the sign of the inequality won't change.

And so we have that 1 + x to the power of n + 1

is greater than or equal to 1 + nx times 1 + x.

Now, we're going to open the brackets and what we'll get is 1 + nx + x + nx squared.

And now we're going to group nx and x into (n + 1)x.

And we're going to remove the summand nx squared.

This summand is positive because x is positive and n is non-negative.

So we can just remove this and we get an inequality

that this is bigger than 1 + (n+1)x.

And so in the end we get that 1 + x to the power of n + 1 is

greater than or equal to 1 + (n + 1)x.

Exactly what we needed.

So we have just proven Bernoulli's inequality in the general case.

Now we're going to apply this inequality to our problem.

So we wondered whether there is such big n that

1.02 in the power of n is bigger than 1,000.

So let's take n equals 50,000.

And see how Bernoulli's inequality will help us.

So 1.02 to the power of 50,000 is the same as 1

+ 0.02 to the power of 50,000.

And now, we can apply Bernoulli's inequality for

n equals 50,000 and x equal to 0.02.

And we'll get that this left part is greater than or equal to 1 + nx.

n is 50,000, and x is 0.02.

50,000 times 0.02 is just 1,000, so

this is equal to 1 + 1,000 and this is bigger than 1,000.

So in the end,

we get that 1.02 to the power of 50,000 is strictly bigger than 1,000.

And so the answer to our problem is yes.

Actually, this number, 1.02 to the power of n,

grows much, much quicker than you would imagine.

And in fact, 1.02 in the power of 349 is already bigger than 1,000.

This is actually the smallest n is 349 when 1.02 is bigger than 1,000.

And what it means that if you get just $1,000 and you earn just 2% every day

from it, you will get more than $1,000,000 by the end of the year.

And to make sense of that, we've prepared separate scripts with

which you can play with this function 1.02 to the power of n.

And you can actually change it to 1.01 and

you can play with different n, and you see how this function grows.

It is an exponential function, that it grows really fast.

And this is why it is very good if you actually can improve something by 2%

every day, you will improve it more than 1,000 times in just one year.

[SOUND]

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.

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

Télécharger dans l'App Store

Disponible sur Google Play