Second Order Recurrence Relation

4 Key excerpts on "Second Order 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 - PDF

  Essential Discrete Mathematics for Computer Science

  • Harry Lewis, Rachel Zax(Authors)
  • 2019(Publication Date)
  • Princeton University Press

    (Publisher)

  Chapter 25 Recurrence Relations Let a 0 , a 1 , ... be any infinite sequence (perhaps of numbers, but perhaps of strings or some other kind of mathematical objects). A recurrence relation is an equation or set of equations that makes it possible to find the value of a n in terms of the values of the a i for i < n . Recurrence relations are accompanied by one or more base cases, giving the value of a i for one or more fixed small values of i . Proofs by induction such as the ones in Chapters 3 and 4 include recur-rence relations. For example, the proof of (3.3) on page 27 relies on the proof that a n = n i = 0 2 i = 2 n + 1 − 1 by means of the recurrence relation and base case a n + 1 = a n + 2 n + 1 a 0 = 1. We also used a recurrence relation in Theorem 23.17 on page 253 to help calculate the number of partitions of an integer n into k parts. Recurrence relations arise naturally in the analysis of algorithms. Let’s start by revisiting (3.12), the formula for the sum of the first n nonnegative integers: n i = 0 i = n · ( n + 1 ) 2 . (25.1) This formula arises in the analysis of the simple sorting algorithm that follows. This selection sort puts a list of numbers in increasing order by repeatedly finding the greatest number in the unprocessed part of the list 278 essential discrete mathematics for computer science and moving it to the beginning of the list. (The name “selection sort” refers to any sorting algorithm that operates by repeatedly selecting the next item and processing it.) We assume that lists are maintained as linked data structures, so that items can be removed and prepended in constant time. The notation A · B will mean a list that contains the elements of list A followed by the elements of list B . Algorithm S ( L ) , to sort a list L : 1. Set M ← λ 2. While L = λ (a) Find the greatest element of L , call it x (b) Let A and B be sublists such that L = A · x · B (c) L ← A · B ; that is, the result of removing x (d) M ← x · M 3.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Methods in Algorithmic Analysis

  • Vladimir A. Dobrushkin(Author)
  • 2016(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 5 Recurrences or Difference Equations Sequences, also known as functions of a discrete variable, appear in many applications of computer science, in numerical analysis, and, naturally, in discrete mathematics. Many of these applications are rooted in practical, engineering problems, where systems have a finite or denumerable state space. Other such scenarios arise when systems change their state at discrete instants of time only. A recurrence is an equation that describes the evolution or behavior of such a function. In this chapter, we present many such equations, and solve only a few special types. More solutions will be introduced and derived in subsequent chapters. A major application that relies on recurrences is the derivation of numerical approximation schemes for differential equations, obtained by a discretization of the continuous problem space; this scenario is not our objective here. However, a special section (§5.6) is dedicated to some numerical approximations. In general, a recurrence is used to find out the properties of a sequence, numeric or symbolic. In our applications, a sequence almost always is a function defined on a set of integers, typically, N = { 0 , 1 , 2 ,... } with values in the set of real (or complex) numbers. Traditionally, terms of sequences are denoted by subscripted symbols such as a n rather than a ( n ) . There will be exceptions, for example, when the subscripts become complex; thus we prefer A ( ⌈ n 2 2 ⌉ ) to A ⌈ n 2 2 ⌉ . A sequence is usually denoted by { a n } ∞ n = 0 or { a n } n greaterorequalslant 0 or simply { a n } , when the range is obvious. If a sequence of interest is finite, it is assumed to be embedded into an infinite one typically padded with zeroes. Infinite sequences also exist outside analysis of algorithms. For example, they arise in com-munication whenever we consider a signal that is sampled at discrete times. A signal might be electrical, mechanical, or optical.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Advances in Applied Combinatorics

  • Stefano Spezia(Author)
  • 2019(Publication Date)
  • Arcler Press

    (Publisher)

  Advances in Applied Combinatorics 168 INTRODUCTION Many number and polynomial sequences can be defined, characterized, evaluated, and classified by linear recurrence relations with certain orders. A number sequence {a n } is called sequence of order 2 if it satisfies the linear recurrence relation of order 2: (1.1) for some nonzero constants p and q and initial conditions a 0 and a 1 . In Mansour [1], the sequence {an} n≥0 defined by [1.1] is called Horadam’s sequence, which was introduced in 1965 by Horadam [2]. The work in [1] also obtained the generating functions for powers of Horadam’s sequence. To construct an explicit formula of its general term, one may use a generating function, characteristic equation, or a matrix method (see Comtet [3], Hsu [4], Strang [5], Wilf [6], etc). In [7], Benjamin and Quinn presented many elegant combinatorial meanings of the sequence defined by recurrence relation [1.1]. For instance, a n counts the number of ways to tile an n-board (i.e., board of length n) with squares (representing 1ss) and dominoes (representing 2s) where each tile, except the initial one has a color. In addition, there are p colors for squares and q colors for dominoes. In this paper, we will present a new method to construct an explicit formula of {an} generated by (1.1). The key idea of our method is to reduce the relation (1.1) of order 2 to a linear recurrence relation of order 1: (1.2) for some constants c 0 and d and initial condition a 0 via geometric sequence. Then, the expression of the general term of the sequence of order 2 can be obtained from the formula of the general term of the sequence of order 1: (1.3) The method and some related results on the generalized Gegenbauer-Humbert polynomial sequence of order 2 as well as a few examples will be given in Section 2. Section 3 will discuss the application of the method to the construction of the identities of sequences of order 2. There is an extension of the above results to higher order cases.

  Sign up to read

  Learn more about book