Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    4.3

    Uploaded by

    a4i20y1j8a
    Recurrence Relations

    Copyright:

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

    4.3

    Uploaded by

    a4i20y1j8a
    6 views12 pages
    Recurrence Relations

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Recurrence Relations

    Copyright:

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

    4.3

    Uploaded by

    a4i20y1j8a
    Recurrence Relations

    Copyright:

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

    CONTENT

    Recurrence Relation &


    Generating function:
    Recursive definition of
    functions,
    Recursive algorithms,
    Method of solving recurrences.
    Recurrence Relation

    A recurrence relation for the sequence {an} is an equation that


    expresses an in terms of one or more of the previous terms of the
    sequence, namely, a0, a1,…, an-1, for all integers n with n ≥ n0, where n0
    is a nonnegative integer.

    an = 2an-1 Recurrence relation


    Recursive
    definition
    a0 = 5 Initial condition

    • A recursive algorithm provides the solution of a problem of size n in term of


    the solutions of one or more instances of the same problem in smaller size.
    • The initial condition specify the terms that precede the first term where
    the recurrence relation takes effect.
    Example 2.1.1
    Let {an} be a sequence that satisfies the recurrence relation
    an = an-1 – an-2 for n = 2, 3,4, and suppose that a0 =3 and a1 = 5.

    List the first four term.


    a0 = 3
    a1 = 5
    a2 = a1 – a0 = ___________________
    a3 = __________________________
    What is a5?
    a5 = __________________________
    EXERCISE 2.1
    1. Let an denotes the nth term of a sequence satisfying the
    given initial condition (s) and the recurrence relation.
    Compute the first four terms of the sequence.

    a1  2, an 3  an  1   2an  1 for n 2


    2
    A

    B 1
    a0 128, an  an  1 for n 1
    4
    C b1 5, bn 7  2bn  1 for n 2
    D
    a1 1, a2 2, an an  1 3  an  2 for n 3
    E
    d1 1, d 2 2, d 3 3, d n d n  1  d n  2  d n  3 for n 4
    Modeling with Recurrence Relation
    • We can use recurrence relation to model a wide variety of
    problems such as

    – Finding a compound interest


    – Counting a population of rabbits
    – Determining the number of moves in the Tower of Hanoi
    puzzle
    – Counting bit strings
    Example 2.1.2: Compound interest
    Suppose that a person deposits RM10,000 in a savings account
    at a bank yielding 11% per year with interest compounded
    annually. Define recursively the compound amount in the
    account at the end of n years.
    Solution:

    Let an : the amount in the account after n years


    Then;
    an = (compound amount at the end of (n -1)th years)
    + (interest for the nth years)
    an = an-1 + 0.11an-1
    = 1.11 an-1
    With initial condition; a0 = 10,000
    Iterative Method
    • Solving the recurrence relation for a function f
    means finding an explicit formula for f (n). The
    iterative method of solving it involves two steps:
    – Apply the recurrence formula iteratively and
    look for the pattern to predict an explicit
    formula
     Forward: start from a0 to an
     Backward : start from an to a0

    – Use Induction to prove that the formula does


    indeed hold for every possible value of the
    integer n.
    Example: Iterative Method
    Using the iterative method, predict a solution for the following
    recurrence relation with the given initial condition.

    S n 2 S n  1 ; S0 1
    Solution:

    S0 1
    S1 2S0
    S 2 2S1 2 2S0  22 S0
    S3 2S 2 2 22 S0  23 S0

    S n 2S n  1 2 2n  1 S0  2n S0 2n ; n 1
    Recall: Mathematical Induction

    Objective: To proof that the statement P(n) is true for each


    integer n ≥ n0

    Steps:

    1. Prove that the statement is true for n = n0.


    2. Assume that the statement is true for n = k.
    3. Prove that the statement is true for n = k + 1.
    4. Conclusion: Therefore, the statement is true
    for each integer n ≥ n0
    Example: Induction
    Using induction, verify the solution for the recurrence relation
    S n 2 S n  1 ; S0 1 is given by S n 2n ; n 1.
    Solution:
    1. Prove that the statement is true for n = n0.
    S1 21 2

    2. Assume that the statement is true for n = k .


    Assume S k 2k ; k 1 is true
    3. Prove that the statement is true for n = k + 1.

    S k 1 2 S k 2 2k  2k 1
    4. Conclusion: Therefore, the statement is true for each integer n ≥ n0
    Generating Function
    • Generating functions are used to represent sequences efficiently by coding the
    terms of a sequence as coefficients of powers of a variable x in a formal power
    series.
    The generating function for the sequence a0, a1,…,ak,… of real
    numbers is the infinite series

    G  x  a0  a1 x    ak x k    ak x k
    k 0
    formal power series

    REMARKS:
    sometimes, this generating function for {ak} is called
    the ordinary generating function of ak
    Example

    The generating function for the following sequences {ak} are


    given by:

    ak 3, G  x   3x k 
    k 0


    ak k  1, G  x   k  1 x k 
    k 0


    ak 2k , G  x   2k x k 
    k 0

    You might also like