Solving a set of recurrence relations A n = B n − 1 + C n − 1 B n = A n + C n − 1 C n = B n + C n − 1 D n = E n − 1 + G n − 1 E n = D n + F n − 1 F n = G n + C n G n = E n + F n − 1 which I would like to solve, with the goal of eventually finding an explicit form of E n . I started out by looking at only A n , B n and C n , and found a formula for A n . A n = 1 / 3 3 ( 2 + 3 ) n − 1 / 3 3 ( 2 − 3 ) n but I cant seem to find the right trick this time.

Question

Solving a set of recurrence relations      A    n    =      B          n      −      1        +      C          n      −      1            B    n    =      A    n    +      C          n      −      1            C    n    =      B    n    +      C          n      −      1            D    n    =      E          n      −      1        +      G          n      −      1            E    n    =      D    n    +      F          n      −      1            F    n    =      G    n    +      C    n        G    n    =      E    n    +      F          n      −      1      which I would like to solve, with the goal of eventually finding an explicit form of       E    n  . I started out by looking at only       A    n  ,       B    n   and       C    n  , and found a formula for       A    n  .      A    n    =  1  /  3      3    (  2  +      3        )    n    −  1  /  3      3    (  2  −      3        )    n  but I cant seem to find the right trick this time.

Amelie Douglas · Accepted Answer

Substitute and eliminate. You already know how to solve a recurrence on one function; eliminate functions from the system until you get to only one, by substituting one function for another.For example, substitute       B          n      −      1       into the definition of       C    n   to get      C    n    =      A          n      −      1        +      C          n      −      2        +      C          n      −      1        .  B  has been eliminated, and we&#039;re one step closer to having an equation involving just   C.By inspection,   A,   B, and   C are mutually defining, and separately   D,   E,   F,   G are mutually defining except for   C. So solve for   C first, using   A and   B, then continue on with just   D,   E,   F,   G.This is very similar to Gaussian elimination, but you have the extra subscripts to deal with in       C          n      −      1      ,       C          n      −      2      , etc.

Brooke Ayala · Accepted Answer

Write without subtractions in indices:                              a                      n            +            1                                              =                  b          n                +                  c          n                                              b                      n            +            1                                              =                  a                      n            +            1                          +                  c          n                                              c                      n            +            1                                              =                  b                      n            +            1                          +                  c          n                                              d                      n            +            1                                              =                  e          n                +                  g          n                                              e                      n            +            1                                              =                  d                      n            +            1                          +                  f          n                                              f          n                                    =                  g          n                +                  c          n                                              g                      n            +            1                                              =                  e                      n            +            1                          +                  f          n                    Define a slew of generating functions like   A  (  z  )  =      ∑          n      ≥      0            a    n        z    n  , multiply each recurrence by       z    n   and sum over   n  ≥  0, then recognize e.g.      ∑          n      ≥      0            a          n      +      1            z    n    =            A      (      z      )      −              a        0              z  This sets up a beautiful linear system of equations for the generating functions, which your tame computer algebra system solves for you:  E  (  z  )  =                    e        0            +      (              c        0            −      7              e        0            +      2              g        0            )      z      +      (              b        0            +      13              e        0            −      8              g        0            )              z        2            +      (              b        0            −              c        0            −      3              e        0            +      2              g        0            )              z        3                    (      1      −      4      z      +              z        2                    )        2            Split into partial fractions (this gets ugly, zeros of the denominator are   2  ±      3  ) and use the generalized binomial theorem to read off the coefficients.

Solving a set of recurrence relations A n </msub> = B n

Answered question

Answer & Explanation

New Questions in Algebra I