During some computations I came up with the following system of linear recurrences:Bn+2=3Bn+AnAn=An−1+Bn−1Here 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 isBn+2=3Bn+∑i=0n−1Bi,which will not help me to solve recurrence. So is there a way I can find B without the summation through n?

Question

During some computations I came up with the following system of linear recurrences:Bn+2=3Bn+AnAn=An−1+Bn−1Here 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&#039;t solve it. The only thing I can do isBn+2=3Bn+∑i=0n−1Bi,which will not help me to solve recurrence. So is there a way I can find B without the summation through n?

Alexandra Haynes · Accepted Answer

You can transform the above equations into equations only in A and only in B: The second equation gives  Bn=An+1−An  applying this to the first equation gives  An+3−An+2=3(An+1−An)+An=3An+1−2An  ⇒An+3=An+2+3An+1−2An  Similar  An=Bn+2−3Bn  Bn+2−3Bn=Bn+1−3Bn−1+Bn−1⇒  Bn+2=Bn+1+3Bn−2Bn−1

Cheryl Stark · Accepted Answer

the equation  Bn+2=3Bn+∑i=0n−1Bi  is of the form  B∗h(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=−∞∞z−nh(n)=z−2−2−11−z=  =z−2−z−1−3+2z1−z  1H(z)=1−z1−z−3z2+2z3=(1−z)(2z−1)(z2−z−1)  perform partial fraction decomposition to get:  1H(z)=−15(z−12)+z−35(−1−z+z2)=  =−15(z−12)+Az−φ+Bz−φ  for some constants A,B and φ=1+52. The solution is then:  g(n)=−1102{n≥1}−n+Aφ{n≥1}n−1+Bφ{n≥1}−n+1  with  g∗h(n)=∑m=−∞∞g(m)h(n−m)=δ(n)  i.e. g(n) is the solution of your difference equation for initial condition B(n)=0 for n&amp;lt;0 and B(0)=1, the solution for other initial condition being found by linearity.

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

Answered question

Answer & Explanation

New Questions in Algebra I