Loading...

Alternating Sum

Course video 39 of 68

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.

Mathematical Thinking in Computer Science

カリフォルニア大学サンディエゴ校

Introduction to Discrete Mathematics for Computer Science 専門講座における 5 の 1 コース

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.

シラバスを表示

学習するスキル

Mathematical Induction, Proof Theory, Discrete Mathematics, Mathematical Logic

講師

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Vladimir Podolskii
Associate Professor

字幕

[SOUND] Hi!

This is the final video about mathematical induction.

And we are going to consider a harder problem here.

And this is actually a good example of a problem where it is unclear how to solve

it without using mathematical induction.

The problem is the following.

We need to prove the equality of an alternating sum and a regular sum.

The alternating sum on the left is 1-1 over 2, + 1 over 3,- 1 over 4,

and so on with alternating pluses and minuses up to 1 over 99- 1 over 100.

And the sum on the right is from 1/51 + 1/52 and up to 1/100.

It is really unclear how to solve this problem directly,

because we could of course try to get all the fractions to the common denominator.

But this common denominator will be a product of 100 numbers, and

it will be huge.

And in the numerator we will have an alternating sum of products,

of 99 numbers, pluses and minuses and

we'll have to do a lot of computations with really huge numbers.

And instead of that, we're going to avoid computations with big numbers at all.

But first we're going to use generalization, so instead of solving this

initial problem, let's solve a more general problem actually.

We're going to prove that the alternating sum 1- 1 over 2 + 1

over 3- 1 over 4, and up to 1 over 2k-1, minus 1 over 2k for

some integer k Is always equal to 1 over k + 1 + 1 over k + 2, and up to 1 over 2k.

And you should notice that for k = 50, this is exactly the same as the initial

problem because the alternating sum on the left goes from 1- 1 over 2,

up to 1 over 2k-1 is 91, 1 over 99- 1 over 100.

So, this is the same alternating sum.

And on the right, the sum starts with 1 over k+1, which is 1 over 51.

And the last summand is 1 over 2k, which is 1 over 100,

which is the same as in the initial problem.

So, this is indeed a more general problem.

And now that we see it is a more general problem, we can actually prove it for

any k using mathematical induction.

And to do that, we'll first prove the induction base for k = 1.

For k = 1, the alternating sum on the left has exactly two summands, 1- 1 or 2.

And the right part just has one sum and

1 over k + 1, where k is the gold one, so it is 1 over 2.

And we see that the alternating sum is equal to the right part.

So, we prove the induction base for k = 1.

And now we want to prove the induction step.

To move from k to k + 1.

And to avoid writing really long formulas,

let's see what changes in the left and the right part when k increases by one.

So we know that for k, the left part is equal to the right part.

And we want to prove that for

k + 1 the left part will also be equal to the right part.

Instead of comparing the whole left and right part for k + 1,

we'll just compare the differences in the left part and in the right part.

And if the initially the left part is equal to the right part,

and the differences are equal than the left part and

right part for k + 1 are also equal.

So for the alternating sum, when we increase k by 1,

we always get two more summands.

We get one with plus and one with minus.

So with plus we have 1 over 2k + 1, and with minus we have 1 over 2(k + 1).

So this is by how much the left part will increase when we increase k by 1.

Now let's look at k + 1 and the right part.

So the right part for k + 1 starts with 1 over k + 2,

and goes up to 1 over 2k + 1.

But I also explicitly wrote the last three summands.

1 over 2k, 1 over 2k + 1, and 1 over 2 times k+ 1.

Now what we can do is a magical trick in math, is we can add 0 to anything and

it will stay the same.

And to add 0 we can actually subtract something and add something.

So in the left we subtract 1 over k+1 and add it back.

And so nothing changes and so we have a equality of the first line and

the second line.

Now I want to rearrange our summands.

We want to notice that starting from the second sum and

in the second line, we get the right part for K.

We get the sum from 1 over k + 1,

1 over k + 2 plus 1 over k + 3 and up to 1 over 2k.

And then we have three more summands which are not in this sum.

Two of them are the two last summands for k + 1.

Those are 1 over 2k + 1 plus 1 over 2 times k + 1.

And also there is the summand that we subtracted in the second line.

1 over k + 1.

So the right part changes by exactly these three last summands.

I over 2k + 1 plus 1 over 2 times k + 1 minus 1 over k + 1.

And we can actually simplify this expression, if we notice

that 1 over 2 times 2k + 1- 1 over k + 1 is the same as -1 over 2 x k + 1.

And so actually, when we rewrite it and simplify it,

we see that the right part, changes from k to k + 1 by the same value.

1 over 2k + 1- 1 over 2 times k + 1 as the left part.

So left part and right part change by the same amount, and

they were the same for k, so they are the same for k + 1.

And we have proven the induction step.

And as we have proven both the induction base and

the induction step from k to k + 1.

We have proven the general statement, and we know that the alternating sum on

the left is equal to the sum on the right for any k.

In particular, it is also true for k equal 50, and so we solve their problem.

As I said, this is the last video about mathematical induction so

it's time to make some conclusions.

We see that mathematical induction is a powerful proof method because we

solved a lot of problems with it.

And some of the problems couldn't be solved without it.

To apply it, we first need to reformulate problem in mathematical terms,

then we need to prove induction base.

Which is basically the proof of our statement for several small values of n.

In most cases just for one smallest value of n.

Then we need to prove the induction step, and in the simple case,

in the weak induction, we just prove from n to plus 1, assuming that this

statement is true for n, we prove that it is also true for n plus 1.

But sometimes we need to apply a strong induction, or complete induction,

when we use induction step from several values of n to n plus 1.

And in this case, we need to remember to also prove induction base for

the corresponding number of smallest values of n,

not just for one but for many as we use in the induction step.

Also, sometimes for induction

we often need to come up with a formula somehow before, proving this formula.

We saw this example in the girl's teacher's problem.

And also, as we saw in this last lecture, we sometimes

need to generalize our problem before we can see that induction can be applied.

So in this problem, we were proving something for a formula with

a alternating sum of 100 summands and the regular sum with 50 summands.

We generalize it for

alternating sum with 2k summands and the regular sum with k summands.

And then we were able to apply induction and prove it for all values of k.

In particular for k equals 50.

So sometimes you need to generalize, and

this makes your problem harder from one point of view.

But it actually makes it simple because then you can apply mathematical induction

and this powerful proof method solves their problem.

See you next week.

[SOUND]

[MUSIC]

Courseraについて

コース、専門分野と世界最高の大学や教育機関からのトップ講師が教えるオンライン学位。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

コーセラは、世界トップクラスの教育を世界中に配信しています。最高峰の大学や組織とのパートナーシップに基づくオンラインコースが提供されています。

© 2019 Coursera (株)すべての権利予約します。

App Storeからダウンロード

Google Playで取得