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 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 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 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 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 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 2. b = 0. The equation has the form We can find ... Obviously, This sequence is a geometric progression. for any n.
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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Examples 1) The characteristic equation: Roots: The general solution: Equations for c 1, c 2 : Solution of the equation:
31 Examples 2) The characteristic equation: Unique root: The general solution: Equations for c 1, c 2 : Solution of the equation :
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 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 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 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 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 The characteristic equation for this recurrence is It has two roots The general solution of the recurrence is
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 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 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 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 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 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.
Последний слайд презентации: 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,....