# Презентация на тему: Discrete Mathematics

1/44
Средняя оценка: 4.3/5 (всего оценок: 99)
Код скопирован в буфер обмена
1

## Первый слайд презентации: Discrete Mathematics

Lecture 9

Изображение слайда
2

## Слайд 2

2 Recurrences Let ( x 0, x 1, x 2,...) be an infinite sequence of numbers in that several initial elements x 0, x 1,..., x k are given; each next element is defined by previous elements according to some rule. This rule is named a recurrence ( recurrence equation or recurrence relation ). We shall consider the linear recurrences with constant coefficients, i.e. equations in which the rule is described by a linear expression.

Изображение слайда
3

## Слайд 3

3 Examples 1) Initial element: x 0 = 1, recurrence: x n = x n -1 + 1 for n > 0. We find: x 1 = x 0 + 1 = 2, x 2 = x 1 + 1 = 3, x 3 = x 2 + 1 = 4, ... Obviously, that is the sequence of all natural numbers.

Изображение слайда
4

## Слайд 4

4 2) Initial element: x 0 = 1, recurrence: x n = 2 x n -1 for n > 0. We find: x 1 = 2 x 0 = 2, x 2 = 2 x 1 = 4, x 3 = 2 x 2 = 8, ... Obviously, that is the sequence of degrees of 2:

Изображение слайда
5

## Слайд 5

5 First order linear recurrences The general linear recurrence of the first order has the form where a and b are given constants, n > 0. If an initial element x 0 is also given then we can compute sequentially the other elements: ...

Изображение слайда
6

## Слайд 6

6 Any element x n, n > 0, is uniquely defined by a, b, and x 0. Can we write a general formula for it? First we shall consider the following two special cases: 1. a = 1. 2. b = 0.

Изображение слайда
7

## Слайд 7

7 1. a = 1. The equation has the form We can find ... Obviously, This sequence is an arithmetic progression. for any n. (It can be easy proved by induction on n ).

Изображение слайда
8

## Слайд 8

8 2. b = 0. The equation has the form We can find ... Obviously, This sequence is a geometric progression. for any n.

Изображение слайда
9

## Слайд 9

9 Now we consider the general case First we shall reduce the equation to a simplified form with a help of the change of unknown where y n is a new unknown, s is a constant which value we shall determine later. (1) ‏ (2) ‏ Substituting of (2) in (1) we get or

Изображение слайда
10

## Слайд 10

10 Let us select such s that i.e. Note that for a = 1 this expression is not defined. But the case a = 1 had been considered previously. Further we suppose that a  1. Then we obtain the equation

Изображение слайда
11

## Слайд 11

11 This equation has a simplest form (case 2), its solution is Because of we obtain and it remains to substitute the expression for s :

Изображение слайда
12

## Слайд 12

12 We don't recommend you to remember this formula. It is rather the solution method. It includes the following three stages. 1. Reduction of equation to the simplest form by the change of unknown x n = y n + s and choice of suitable value for s. 2. Solving of the obtained simplest equation. 3. Return to the former unknown x n.

Изображение слайда
13

## Слайд 13

13 Note that the solution has the form where c 1 and c 2 are some constants. We see that the dependence of x n on n is expressed as an exponential function.

Изображение слайда
14

## Слайд 14

14 Example: Towers of Hanoi The French mathematician Edouard Lucas invents in 1883 the following problem. Eight disks of different sizes are threaded on one of three pegs in order of size decreasing. Goal is to transpose the disks in the same order onto another peg. It is allowed to move only one disk at a time and it is forbidden to put a larger disk on the smaller one. How many steps are needed for this? (A step is a movement of a disk)‏

Изображение слайда
15

## Слайд 15

15 Let us consider this problem in a general form when there are n disks. Let T n be the minimum number of steps needed to move n disks from one peg to another. Obviously, T 1 = 1. It is easy to see that T 2 = 3:

Изображение слайда
16

## Слайд 16

16 We can transpose three disks in the following manner: 1) move two disks as above (3 steps)‏ 2) move the largest disk (1 step)‏ 3) move two disks again (3 steps) ‏ Thus T 3 = 3 + 1 + 3 = 7.

Изображение слайда
17

## Слайд 17

17 In general case we must transpose n – 1 smaller disks before we move the largest disk. It requires T n - 1 steps. After moving the largest disk it is necessary again to transpose n – 1 smaller disks. It requires also T n - 1 steps. Hence we have the recurrence If we let then the equality is also valid for n = 1.

Изображение слайда
18

## Слайд 18

18 We solve this equation in three described stage. 1. Reduction. then Let Take s =  1 and get the equation 2. Solving of simplified equation. 3. Return to the former unknown. Answer:

Изображение слайда
19

## Слайд 19

19 Second order linear recurrences General linear recurrence equation of second order has the form where a, b, and c are given constants, n > 1. We shall consider first the homogeneous equation ( c = 0): (3) ‏

Изображение слайда
20

## Слайд 20

20 If we know the two initial elements x 0 and x 1 then we are able to compute sequentially the other elements: and so on. Every element x n, n > 1, is uniquely defined by a, b, x 0, x 1. We also can obtain a general formula for x n in this case.

Изображение слайда
21

## Слайд 21

21 We shall look for a solution in the exponential form: where  is unknown constant (the idea goes from the solutions form of the first order recurrence). Substitution of this expression in the equation (3) gives It may be reduced by and we get

Изображение слайда
22

## Слайд 22

22 Thus  must be a root of the equation called a characteristic equation. There are the two possibilities. A. The characteristic equation has two distinct roots  1 and  2. B. There is one root  1 =  2. (the discriminant is zero: a 2 + 4 b = 0).

Изображение слайда
23

## Слайд 23

23 A. The characteristic equation has two distinct roots  1 and  2. Then both sequences and satisfy the equation (3). But we need solution with given x 0, x 1. Can we achieve it?

Изображение слайда
24

## Слайд 24

24 The homogeneous linear equation has two following important properties: 1) if a sequence satisfies the equation (3) and a is some constant then the sequence also satisfies this equation (to verify this statement it is sufficient to substitute ax n in the equation instead of x n );

Изображение слайда
25

## Слайд 25

25 both satisfy the equation (3) then the sequence also satisfies this equation. 2) if sequences and (If we substitute in the equation instead of x n then we get and it is fulfilled since and ) ‏

Изображение слайда
26

## Слайд 26

26 Due to properties 1), 2) we may affirm that the sequence satisfies the equation (3) for any constants c 1, c 2. This sequence is called a general solution of an equation (3). Can we fit c 1, c 2 in such a way that two initial elements of the sequence would be x 0 and x 1 ? We shall try:

Изображение слайда
27

## Слайд 27

27 Thus we get a system of two linear equations with two unknowns c 1, c 2 : The determinant of this system is as Hence there exists a unique solution c 1, c 2 and we obtain a solution of equation (3) with given start-up values.

Изображение слайда
28

## Слайд 28

28 B. The characteristic equation has a single root . In this case the general solution has the form (without a proof). Constants c 1 and c 2 may be found using the initial values:

Изображение слайда
29

## Слайд 29

29 So we have the following algorithm for solving of a linear homogeneous recurrence equation of the second order. 1. Write the characteristic equation and solve it. 2a. If the characteristic equation has two distinct roots  1 and  2 then write the general solution in the form 2b. If the characteristic equation has a unique root  then write the general solution in the form 3. Write equation system for c 1, c 2 using given initial values x 0, x 1 and solve it. 4. Substitute the found values of constants in the general solution.

Изображение слайда
30

## Слайд 30

30 Examples 1) ‏ The characteristic equation: Roots: The general solution: Equations for c 1, c 2 : Solution of the equation:

Изображение слайда
31

## Слайд 31

31 Examples 2) ‏ The characteristic equation: Unique root: The general solution: Equations for c 1, c 2 : Solution of the equation :

Изображение слайда
32

## Слайд 32

32 Inhomogeneous equation An inhomogeneous linear recurrence of the second order may be reduced to homogeneous equation in the same way as in the case of recurrences of the first order. We introduce a new unknown y n and select such s that the constant term vanishes:

Изображение слайда
33

## Слайд 33

33 If a + b  1 then s exist and we obtain a homogeneous equation, solve it, and then return to former unknown. If a + b = 1 then s does not exist. In this case one has to make the other change of unknown: and again select such s that equation becomes homogeneous.

Изображение слайда
34

## Слайд 34

34 Fibonacci numbers Leonardo Fibonacci (1170 – 1250) also known as Leonardo Pisano, was an Italian mathematician. He is the best known due to the discovery of the Fibonacci numbers and because of his role in the introduction of the modern Arabic decimal system for writing numbers in Europe.

Изображение слайда
35

## Слайд 35

35 The Fibonacci numbers are elements of the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,.... In this sequence each element beginning with the third is equal to the sum of two preceding elements: 1 = 1 + 0, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2, ...

Изображение слайда
36

## Слайд 36

36 If we denote the n - th element of the sequence by F n ( n = 0, 1, 2,... ) then the rule may be written as It is a linear recurrence equation of the second order. There are also initial values and we can find a general formula for the Fibonacci number.

Изображение слайда
37

## Слайд 37

37 The characteristic equation for this recurrence is It has two roots The general solution of the recurrence is

Изображение слайда
38

## Слайд 38

38 Now we use the initial values for writing the equations for the constants c 1 and c 2 : Solving this system we find and obtain the formula for the Fibonacci numbers:

Изображение слайда
39

## Слайд 39

39 A binary word containing no two consecutive 1’s will be called a sparse word. For example, the word 0100101000101 is sparse while words 0101100011 and 0011110 are not sparse. Denote the number of all sparse words of length n by U n. Example: Sparse words

Изображение слайда
40

## Слайд 40

40 For small n we have: 0 1 2 3 4 Sparse words n U n λ 0 1 00 01 10 000 001 010 100 101 0000 0001 0010 0100 0101 1000 1001 1010 1 2 3 5 8

Изображение слайда
41

## Слайд 41

41 What is U 5 ? If  is a sparse word of length 5 and the first letter of  is 0 then  = 0 β where β is a sparse word of length 4. There are 8 of such words: 0 0000 0 0001 0 0010 0 0100 0 0101 0 1000 0 1001 0 1010

Изображение слайда
42

## Слайд 42

42 If the first letter in  is 1 then the second letter must be 0 and  = 10 γ where γ is any sparse word of length 3. There are 5 of such words: 10 000 10 001 10 010 10 100 10 101 At all we have

Изображение слайда
43

## Слайд 43

43 In general case let  be a sparse word of the length n. If the first letter of  is 0 then  = 0 β where β is any sparse word of length n  1. There are U n - 1 such words. If the first letter in  is 1 then the second letter must be 0 and  = 10 γ where γ is any sparse word of length n  2. There are U n - 2 such words.

Изображение слайда
44

## Последний слайд презентации: Discrete Mathematics

44 Thus we obtain the recurrence for these numbers: for n ≥ 2. It is the same recurrence as for Fibonacci numbers. However the start-up values are other: U 0 = 1, U 1 = 2. But we see that U 0 and U 1 coincide with two successive Fibonacci numbers: Consequently, for n = 0, 1, 2,....

Изображение слайда