During some computations I came up with the following system of linear recurrences: B_{n+2}

Ravi Stein

Ravi Stein

Answered question

2022-02-24

During some computations I came up with the following system of linear recurrences:
Bn+2=3Bn+An
An=An1+Bn1
Here I am trying to find the solution for B (hoping to get some sort of homogeneous equation, find it roots and get the closed form formula).
But I can't solve it. The only thing I can do is
Bn+2=3Bn+i=0n1Bi,
which will not help me to solve recurrence. So is there a way I can find B without the summation through n?

Answer & Explanation

Alexandra Haynes

Alexandra Haynes

Beginner2022-02-25Added 10 answers

You can transform the above equations into equations only in A and only in B: The second equation gives
Bn=An+1An
applying this to the first equation gives
An+3An+2=3(An+1An)+An=3An+12An
An+3=An+2+3An+12An
Similar
An=Bn+23Bn
Bn+23Bn=Bn+13Bn1+Bn1
Bn+2=Bn+1+3Bn2Bn1
Cheryl Stark

Cheryl Stark

Beginner2022-02-26Added 7 answers

the equation
Bn+2=3Bn+i=0n1Bi
is of the form
Bh(n)=0
where h(n)=δ(n+2)2δ(n)k=0δ(n) is a linear filter. the general way to solve this is similar as the method of using the Laplace transform for solving linear differential equations. the discrete version of the Laplace transform is the the Z-transform:
H(z)=n=znh(n)=z2211z=
=z2z13+2z1z
1H(z)=1z1z3z2+2z3=(1z)(2z1)(z2z1)
perform partial fraction decomposition to get:
1H(z)=15(z12)+z35(1z+z2)=
=15(z12)+Azφ+Bzφ
for some constants A,B and φ=1+52. The solution is then:
g(n)=1102{n1}n+Aφ{n1}n1+Bφ{n1}n+1
with
gh(n)=m=g(m)h(nm)=δ(n)
i.e. g(n) is the solution of your difference equation for initial condition B(n)=0 for n<0 and B(0)=1, the solution for other initial condition being found by linearity.

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?