Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Week 4 - (Part B) Recurrence Relations

    Uploaded by

    Game Account
    This document provides an overview of recurrence relations and methods for solving them. It covers key topics such as: - Defining sequences and recurrence relations, including examples of arithmetic and geometric sequences. - Using summation notation to represent partial sums of sequences. - Formulating recurrence relations for arithmetic and geometric sequences based on their common differences or ratios. - Methods for solving recurrence relations, including telescoping, iteration, and back tracking approaches. Examples are provided to illustrate each method. - The document is divided into sections covering sequences, summation notation, formulating relations, and solving techniques like telescoping, iteration, and back tracking.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Week 4 - (Part B) Recurrence Relations

    Uploaded by

    Game Account
    8 views12 pages
    This document provides an overview of recurrence relations and methods for solving them. It covers key topics such as: - Defining sequences and recurrence relations, including examples of arithmetic and geometric sequences. - Using summation notation to represent partial sums of sequences. - Formulating recurrence relations for arithmetic and geometric sequences based on their common differences or ratios. - Methods for solving recurrence relations, including telescoping, iteration, and back tracking approaches. Examples are provided to illustrate each method. - The document is divided into sections covering sequences, summation notation, formulating relations, and solving techniques like telescoping, iteration, and back tracking.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of recurrence relations and methods for solving them. It covers key topics such as: - Defining sequences and recurrence relations, including examples of arithmetic and geometric sequences. - Using summation notation to represent partial sums of sequences. - Formulating recurrence relations for arithmetic and geometric sequences based on their common differences or ratios. - Methods for solving recurrence relations, including telescoping, iteration, and back tracking approaches. Examples are provided to illustrate each method. - The document is divided into sections covering sequences, summation notation, formulating relations, and solving techniques like telescoping, iteration, and back tracking.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    8 views12 pages

    Week 4 - (Part B) Recurrence Relations

    Uploaded by

    Game Account
    This document provides an overview of recurrence relations and methods for solving them. It covers key topics such as: - Defining sequences and recurrence relations, including examples of arithmetic and geometric sequences. - Using summation notation to represent partial sums of sequences. - Formulating recurrence relations for arithmetic and geometric sequences based on their common differences or ratios. - Methods for solving recurrence relations, including telescoping, iteration, and back tracking approaches. Examples are provided to illustrate each method. - The document is divided into sections covering sequences, summation notation, formulating relations, and solving techniques like telescoping, iteration, and back tracking.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 12

    Week 4: Recurrence Relations

    Section…………………………………………………………………………………………….Page

    Section 1: Sequences and Recurrence Relations ..………………………………………………...2

    Section 2: Sigma Notation and Partial Sums of Sequences ..……………………………………..3

    Section 3: Formulating Recurrence Relations and Solving Recurrence Relations………………..5

    Section 3.1: Formulating Recurrence Relations …………………………………………………..5

    Section 3.2: Solving Recurrence Relations ……………………………………………………….7

    Section 3.2.1: Telescopic Method ………………………………………………………………....7

    Section 3.2.2: Iteration Method ……………………………………………………………………8

    Section 3.2.3: Back Tracking Method ………………….………………………………………….9

    Section 3.2.4: Characteristic Root Method......................................................................................10

    Bibliography ……………………………………………………………………………………….12

    UU-MTH- 1005 - Discrete Mathematics Page 1


    Section 1: Sequences and Recurrence Relations

    Sequences
    A sequence is an ordered set of numbers. For example: 1, 2, 3, 4, … is an example of a sequence.

    We can see that, in the sequence given above, it is easy to tell what number comes next because the
    sequence follows a particular pattern. This is exactly what we are going to look at: sequences that
    follow a particular pattern.

    But sometimes it is not easy to tell what number comes next as in the sequence: 1, 5, 9, 13, 17. As a
    result, it is preferable to use a formula or rule which clearly defines the terms of the sequence.

    Before we look at the formulae, we need to see that terms of the sequences are usually labelled with
    subscripts as,

    so that , where , can be used to represent the .

    Sequences with a Formula for the term


    For ,

     :
     :
     : ( ) ( ) ( )

    We can see that the formula helps to determine any number, at any position, in the sequence
    without having to first list all the previous numbers.

    Recurrence Relations
    A recurrence relation is a formula relating a term of the sequence to previous terms and to an initial
    condition (or a list of first few terms of the sequence). But a recurrence relation together with an initial
    condition is altogether called a recursive definition. For example,

     with , where
     with , where

    UU-MTH- 1005 - Discrete Mathematics Page 2


    For second one, we have the initial term as 4 and each term of the sequence will be 2 more than the
    previous one, thereby giving:

    Section 2: Sigma Notation and Partial Sums of


    Sequences

    Partial Sums of Sequences


    Given the following formula of the sequence,

    We have:

    Therefore, we have a sequence 2, 4, 6, 8, …

    If we were to pick the first three numbers/terms of the sequence and add them, we would have 2+5+6.
    This is called a partial sum of the sequence, denoted by , because not all numbers of the sequence
    have been added.

    From the partially determined sequence above, we would have some partial sums as

    To generalize, we would have

    UU-MTH- 1005 - Discrete Mathematics Page 3


    …

    A partial sum of the sequence can be represented in a compact form called sigma notation and the
    Greek capital letter sigma is used to mean “sum up”.

    Examples

    Example

    Find the following summations

    i)
    ii)

    Solutions

    i)
    ii)

    UU-MTH- 1005 - Discrete Mathematics Page 4


    Section 3: Formulating Recurrence Relations and
    Solving Recurrence Relations

    Section 3.1: Formulating Recurrence Relations


    We will look at formulating recurrence relations and closed formulae of arithmetic sequences and
    geometric sequences. The recurrence relations will definitely have their initial values presented as well.

    Arithmetic Sequences
    An arithmetic sequence is a sequence in which there is a constant difference (also called a common
    difference) between any two consecutive terms. Given that the initial term of the sequence is
    and the common difference is , then we have

    with as a recurrence relation with an initial term

    and

    as the closed formula for the sequence

    Example 3.1

    Given the sequences below, find for each a recurrence relation and closed formula by assuming that the
    initial term is the first listed value in the sequence.

    i) 1, 5, 9, 13, 17, 21, …


    ii) 15, 13, 11, 9, 7, 5, ..

    Solution 3.1

    i) For the values we have in sequence, we have


    . This indicates that the sequence is an arithmetic sequence since the
    difference between any two consecutive terms/values in the sequence is constant.

    Therefore, the common difference is 4 and the initial term is 1.

    The recurrence relation is with


    The closed formula is

    UU-MTH- 1005 - Discrete Mathematics Page 5


    ii) We have . This
    indicates that the sequence is an arithmetic sequence since the difference between any two
    consecutive terms/values in the sequence is constant.

    Therefore, the common difference is -2 and the initial term is 15.

    The recurrence relation is with


    The closed formula is

    Geometric Sequences
    A geometric sequence is a sequence in which there is a constant quotient (called a common ratio)
    between any two consecutive terms. Given that the initial term of the sequence is and the
    common ratio is , then we have

    with as a recurrence relation with an initial term

    and

    as the closed formula for the sequence.

    Example 3.2

    Given the sequences below, find for each a recurrence relation and closed formula by assuming that the
    initial term is the first listed value in the sequence.

    3, 6, 12, 24, 48, 96, …

    Solution 3.2

    For the values we have in sequence, we have .


    This indicates that the sequence is a geometric sequence since the quotient between any two
    consecutive terms/values in the sequence is constant.

    Therefore, the common ratio is 2 and the initial term is 3.

    The recurrence relation is with


    The closed formula is

    UU-MTH- 1005 - Discrete Mathematics Page 6


    Section 3.2: Solving Recurrence Relations

    Solving a recurrence relation is about finding a closed formula (a function of ) which satisfies the
    recurrence relation and its initial condition. To solve recurrence relations we will look at three different
    methods for three different cases.

    Section 3.2.1: Telescoping Method


    Telescoping method shows a way to solve recurrence relations of the form where
    has a known closed formula. If we rewrite the recurrent relation as
    , the left-hand side will always give you and the right hand
    side sum will always need that we know its closed formula. When all terms on the left hand
    side cancel out by subtraction to leave only , we say the recurrence relation has telescoped.

    Example 3.3

    Solve the recurrence relation whose initial term is .

    Solution 3.3

    Rewriting the above expression under sums (partial sums), we have

    The closed formula for the recurrent relation is therefore going to be

    UU-MTH- 1005 - Discrete Mathematics Page 7


    Section 3.2.2: Iteration Method
    When we have, for example, a recurrence relation of the form , the sums on the left
    hand side will not telescope. It is for this case that we will need the iteration method to find the closed
    formula for the recurrence relation.

    Here, we will have to iterate the process of finding the next term by starting with a known initial
    condition up until we have .

    Example 3.4

    Solve the recurrence relation with .

    Solution 3.4

    Simplifying further, we will have

    UU-MTH- 1005 - Discrete Mathematics Page 8


    Therefore, the closed formula will be

    Section 3.2.3: Back Tracking Method


    Using the back tracking method, the closed formula for the recurrence relation is determined from the
    term equation given, which has lower terms in the sequence. This has to do with taking a linear
    recurrence defining and replacing the terms with a relation that defines
    (where at a each corresponding stage gets replaced with …).

    Let us look at an example to understand better:

    Example 3.5

    Solve the following linear recurrence relation using back tracking method
    with

    Solution 3.5

    First, we have

    And then, by taking the linear recurrence relation and replacing the terms , we
    have

    UU-MTH- 1005 - Discrete Mathematics Page 9


    Finally, the closed formula is
    because

    Section 3.2.4: The Characteristic Root Method

    The characteristic root method is used to solve linear homogeneous recurrence relations with constant
    coefficients.

    Linear homogeneous recurrence relations with constant coefficients

    A recurrence relation is a linear homogeneous relation of degree if it is of the form

    where are constant coefficients.

    Any given linear homogeneous relation of degree is always associated with a polynomial of degree
    which we call a characteristic equation and it is of the form

    We have a characteristic equation of degree which means, solving for it, we will have to find its
    roots .

    Linear homogeneous recurrence relations of degree 2


    A linear homogeneous recurrence relation of degree is of the form and its
    characteristic equation will be of the form .

    The Characteristic Root Method

    The linear homogeneous recurrence relation of degree 2, having the form , can
    be solved using the characteristic root method.

    UU-MTH- 1005 - Discrete Mathematics Page 10


    Definition:

    Given a recurrence relation , the characteristic polynomial is

    giving the characteristic equation:

    If and are two distinct roots of the characteristic polynomial, i.e. solution to the characteristic
    equation, then the solution to the recurrence relation is

    If , then the solution to the recurrent relation will be

    Where and are constants determined by the initial conditions.

    Example 3.6

    Solve the recurrence relation with and .

    Solution 3.6

    The recurrence relation is from which we take the characteristic equation

    When we factorise, we get ;

    Solving for , we get and as characteristic roots.

    Therefore, the solution to the recurrence relation will have the form

    To solve for a and b, we plug n=0 and n=1 in the solution form above to get a system of equations with
    two unknowns:

    Solving this system, we get and , which finally gives the solution to the recurrence
    relation as

    UU-MTH- 1005 - Discrete Mathematics Page 11


    Bibliography

    Gersting J. L. (2014). Mathematical Structures for Computer Science (7th ed.).


    W.H. Freeman and Company.

    Levin O. (2017). Discrete Mathematics: An Open Introduction . (2th ed.).


    University of Northern Colorado

    Rosen K. H. (2011). Discrete Mathematics and its applications (7th ed.).


    McGraw Hill Education (India) Private Limited

    Susanna S. E. (2010). Discrete Mathematics with Applications. (4th ed.).


    Brooks/Cole Cengage Learning

    UU-MTH- 1005 - Discrete Mathematics Page 12

    You might also like