Recurrence Relation

2 Key excerpts on "Recurrence Relation"

• 

  eBook - ePub

  Introductory Discrete Mathematics

  • V. K . Balakrishnan(Author)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  Recurrence Relations

  3.1    INTRODUCTION

  Consider a sequence a0 , au a2 , . . . , where ar is the solution of a certain combinatorial problem that depends on the input r. In Chapter 2 we discussed some methods to compute ar using generating functions. In some cases it will be possible to reduce the computation of the rth term of the sequence to earlier members of the sequence if ar can be expressed as a function of the earlier elements of the sequence. For example, consider the arithmetic progression sequence 4, 7, 10, 13, 16, . . . , where the initial number a0 is 4 and the common difference d is 3. Then the rth term of the sequence can be expressed in terms of the (r – l)th term by the equation ar = a

  r

  –1 , + d. This equation is an example of a Recurrence Relation. The condition a0 = 4 is called the initial condition of this relation. Obviously, once the initial condition and the common difference are known any arbitrary term can be obtained by computing a1 , a2 , . . . , sequentially. Or we can obtain the rth term by solving the Recurrence Relation. In this case the solution is ar = 4 + 3r, where r is any nonnegative integer. Similarly, if we take the geometric progression sequence 4, 4.3, 4.32 , 4.33 . . . , the Recurrence Relation is ar = 3 . ar–1 , with initial condition a0 = 4 and the solution is ar = 4 . 3

  r

  .

  Recurrence Relations and Difference Equations

  The first difference d(an ) of a sequence {an } of real numbers is the difference an –an–1 .The second difference d2 (an ) is d(an ) – d(an –1 ), which is equal to an – 2an-1 + an–2 . More generally the kth difference dk (an ) is dk- 1 (an ) – dk–1 (an _x ) . A difference equation is an equation involving an and its differences. For example, 3d2 (an ) + 2d(an ) + 7an = 0 is a second-order homogeneous difference equation. Observe that every ai , (i = 0, 1, 2, . . . ,n – 1) can be expressed in terms of an and these differences because an– 1 = an – d(an );

  and so on. Thus every Recurrence Relation can be formulated as a difference equation. On the other hand, using the definition of these differences, any difference equation can be formulated as a Recurrence Relation. For instance, the difference equation 3d2 (an ) + 2d(an ) + 7an = 0 can be expressed as the Recurrence Relation 12a

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Combinatorial Reasoning

  An Introduction to the Art of Counting

  • Duane DeTemple, William Webb(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  5 Recurrence RelationS

  5.1 INTRODUCTION

  Many—indeed, most—of the sequences h0 , h1 , h2 , …, hn , … encountered in earlier chapters satisfy a Recurrence Relation. In other words, if initial values of the sequence h0 , h1 , h2 , …, h

  k − 1

  either are given to us or can be determined, then every additional term of the sequence is given by a function hn = f(h0 , h1 , h2 , …, h

  n − 1

  ), n ≥ k, which depends only on earlier terms of the sequence.

  A simple example is the Recurrence Relation hn = αh

  n − 1

  , n ≥ 1, where an initial condition h0 = A is to be satisfied. Since each new term depends on just the preceding term, this is a Recurrence Relation of first order. Iteration shows that hn = αh

  n − 1

  = α2 h

  n − 2

  = … = α

  n

  h0 , so the solution is the geometric sequence hn = Aα

  n

  , n ≥ 0.

  In Section 5.2, we will investigate the Fibonacci Recurrence Relation hn = h

  n − 1

  + h

  n − 2

  , n ≥ 2. Each additional term of the sequence is determined by the previous two terms, so this is an example of a second-order Recurrence Relation. The initial conditions h0 = 0 and h1 = 1 correspond to the Fibonacci number sequence 0, 1, 1, 2, 3, 5, 8, …, and the initial conditions h0 = 2 and h1 = 1 correspond to the Lucas sequence 2, 1, 3, 4, 7, 11, ….

  In Section 5.3, general second-order Recurrence Relations of the form hn = a1 h

  n − 1

  + a2 h

  n − 2

  ,  n ≥ 2 are considered, where a1 and a2 are constants. This is known as a second-order linear homogeneous Recurrence Relation with constant coefficients. Mathematical induction shows that the solution is uniquely specified when two initial conditions h0 = A, h1 = B are satisfied.

  In Section 5.4, we extend our methods to solve Recurrence Relations of arbitrary order k that have the form

  (5.1)

  where a1 , a2 , …, ak are constants. A Recurrence Relation with the form of (5.1) is described as a linear homogeneous Recurrence Relation of order k with constant coefficients.

  Sign up to read

  Learn more about book