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

Despiniosnt

Despiniosnt

Answered question

2022-05-21

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.

Answer & Explanation

Amelie Douglas

Amelie Douglas

Beginner2022-05-22Added 8 answers

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'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

Brooke Ayala

Beginner2022-05-23Added 4 answers

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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?