in Combinatory edited by
1,205 views
0 votes
0 votes

Solve the simultaneous recurrence relations

  • $a_{n} = 3a_{n-1} + 2b_{n-1}$
  • $b_{n} = a_{n-1} + 2b_{n-1}$

with $a_{0} = 1 \: \text{and}\: b_{0} = 2.$

in Combinatory edited by
by
1.2k views

1 Answer

2 votes
2 votes

$a_{1}=3a_{0}+2b_{0}=3+4=7$

Now,

$a_{n}-b_{n}=3a_{n-1}-a_{n-1}$

$a_{n}-2a_{n-1}=b_{n}\ \ ................(1)$


Substituted the value of $b_{n}$ in first recurrence relation

$a_{n}=3a_{n-1}+2(a_{n-1}-2_{n-2})$

$a_{n}=5a_{n-1}-4a_{n-2}$

Now, solving this linear homogeneous recurrence relation :

$r^n=5r^{n-1}-4r^{n-2}$

Divide by $r^{n-2}$ on both sides

$r^2=5r-4$

$r^2-5r+4=0$

$r=1,4$

$a_{n}=\alpha_{1}(1)^n+\alpha_{2}(4)^n$

$a_{0}=1=\alpha_{1}+\alpha_{2}$

$a_{1}=7=\alpha_{1}+4\alpha_{2}$

Solving both equations gives : $\alpha_{1}=-1, \alpha_{2}=2$

$\therefore a_{n}=-1+2(4^n)$


Using $(1)$

$b_{n}=-1+2(4)^n-2(-1+2(4)^{n-1})$

$b_{n}=-1+2(4)^n+2-4(4)^{n-1}$

$b_{n}=1+2(4)^n-4^n$

$b_{n}=1+4^n$

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true