Question and Answers Forum

All Questions      Topic List

Algebra Questions

Previous in All Question      Next in All Question      

Previous in Algebra      Next in Algebra      

Question Number 3565 by Yozzii last updated on 15/Dec/15

Define the sequence {a_n } by the  recurrence equation                      a_(n+1) =pa_n +qa_(n−1)   (n≥1)  where p,q∈C−{0} and   a_0 =α , a_1 =β    α,β∈C.  Find a_n  in terms of n.

$${Define}\:{the}\:{sequence}\:\left\{{a}_{{n}} \right\}\:{by}\:{the} \\ $$$${recurrence}\:{equation}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:{a}_{{n}+\mathrm{1}} ={pa}_{{n}} +{qa}_{{n}−\mathrm{1}} \:\:\left({n}\geqslant\mathrm{1}\right) \\ $$$${where}\:{p},{q}\in\mathbb{C}−\left\{\mathrm{0}\right\}\:{and}\: \\ $$$${a}_{\mathrm{0}} =\alpha\:,\:{a}_{\mathrm{1}} =\beta\:\: \\ $$$$\alpha,\beta\in\mathbb{C}. \\ $$$${Find}\:{a}_{{n}} \:{in}\:{terms}\:{of}\:{n}.\: \\ $$$$ \\ $$$$ \\ $$

Answered by prakash jain last updated on 16/Dec/15

a_0 =α  a_1 =β  a_n =pa_(n−1) +qa_(n−2)   x^2 −px−q=0⇒x=((p±(√(p^2 +4q)))/2)  assume p^2 +4q>0  a_n =k_1 (((p+(√(p^2 +4q)))/2))^n +k_2 (((p−(√(p^2 +4q)))/2))^n   k_1 +k_2 =α⇒k_2 =α−k_1   k_1 (((p+(√(p^2 +4q)))/2))+k_2 (((p−(√(p^2 +4q)))/2))=β  k_1 (((p+(√(p^2 +4q)))/2))−k_1 (((p−(√(p^2 +4q)))/2))+α(((p−(√(p^2 +4q)))/2))=β  k_1 (√(p^2 +4q)) =β−α(((p−(√(p^2 +4q)))/2))  k_1 =(β/(√(p^2 +4q)))−((αp)/(2(√(p^2 +4a))))+(α/2)  k_2 =(α/2)−(β/(√(p^2 +4q)))+((αp)/(2(√(p^2 +4a))))  a_n =k_1 (((p+(√(p^2 +4q)))/2))^n +k_2 (((p−(√(p^2 +4q)))/2))^n

$${a}_{\mathrm{0}} =\alpha \\ $$$${a}_{\mathrm{1}} =\beta \\ $$$${a}_{{n}} ={pa}_{{n}−\mathrm{1}} +{qa}_{{n}−\mathrm{2}} \\ $$$${x}^{\mathrm{2}} −{px}−{q}=\mathrm{0}\Rightarrow{x}=\frac{{p}\pm\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}} \\ $$$${assume}\:{p}^{\mathrm{2}} +\mathrm{4}{q}>\mathrm{0} \\ $$$${a}_{{n}} ={k}_{\mathrm{1}} \left(\frac{{p}+\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)^{{n}} +{k}_{\mathrm{2}} \left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)^{{n}} \\ $$$${k}_{\mathrm{1}} +{k}_{\mathrm{2}} =\alpha\Rightarrow{k}_{\mathrm{2}} =\alpha−{k}_{\mathrm{1}} \\ $$$${k}_{\mathrm{1}} \left(\frac{{p}+\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)+{k}_{\mathrm{2}} \left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)=\beta \\ $$$${k}_{\mathrm{1}} \left(\frac{{p}+\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)−{k}_{\mathrm{1}} \left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)+\alpha\left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)=\beta \\ $$$${k}_{\mathrm{1}} \sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}\:=\beta−\alpha\left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right) \\ $$$${k}_{\mathrm{1}} =\frac{\beta}{\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}−\frac{\alpha{p}}{\mathrm{2}\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{a}}}+\frac{\alpha}{\mathrm{2}} \\ $$$${k}_{\mathrm{2}} =\frac{\alpha}{\mathrm{2}}−\frac{\beta}{\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}+\frac{\alpha{p}}{\mathrm{2}\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{a}}} \\ $$$${a}_{{n}} ={k}_{\mathrm{1}} \left(\frac{{p}+\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)^{{n}} +{k}_{\mathrm{2}} \left(\frac{{p}−\sqrt{{p}^{\mathrm{2}} +\mathrm{4}{q}}}{\mathrm{2}}\right)^{{n}} \\ $$

Commented by Yozzii last updated on 15/Dec/15

A generating function approach can  be used?

$${A}\:{generating}\:{function}\:{approach}\:{can} \\ $$$${be}\:{used}? \\ $$

Commented by prakash jain last updated on 16/Dec/15

Thanks for the hint. I didn′t think about it  yet.

$$\mathrm{Thanks}\:\mathrm{for}\:\mathrm{the}\:\mathrm{hint}.\:\mathrm{I}\:\mathrm{didn}'\mathrm{t}\:\mathrm{think}\:\mathrm{about}\:\mathrm{it} \\ $$$$\mathrm{yet}.\: \\ $$

Commented by Rasheed Soomro last updated on 17/Dec/15

Where has x^2 −px−q=0 come?

$${Where}\:{has}\:{x}^{\mathrm{2}} −{px}−{q}=\mathrm{0}\:{come}? \\ $$

Commented by Rasheed Soomro last updated on 17/Dec/15

Is tbis ′ generating function approach ′ ?  I didn′t understand.

$${Is}\:{tbis}\:'\:{generating}\:{function}\:{approach}\:'\:? \\ $$$${I}\:{didn}'{t}\:{understand}. \\ $$

Commented by Yozzii last updated on 17/Dec/15

No. This solution is based on a   theorem on difference equations   of the form       ta_(n+1) +ra_n +ca_(n−1) =0.

$${No}.\:{This}\:{solution}\:{is}\:{based}\:{on}\:{a}\: \\ $$$${theorem}\:{on}\:{difference}\:{equations}\: \\ $$$${of}\:{the}\:{form}\: \\ $$$$\:\:\:\:{ta}_{{n}+\mathrm{1}} +{ra}_{{n}} +{ca}_{{n}−\mathrm{1}} =\mathrm{0}. \\ $$

Commented by Yozzii last updated on 17/Dec/15

Let t,r,c be constants, t≠0, in the  recurrence relation             ta_(n+1) +ra_n +ca_(n−1) =0    (n≥1)  defining the sequence {a_n } with   a_0 =f and a_1 =h.  Consider the auxiliary equation              tλ^2 +rλ+c=0  whose roots are α and β.  The general term a_n  of the sequence  is then given by                           a_n =Aα^n +Bβ^n   (n≥0)  if α≠β.  If  α=β≠0, a_n =(An+B)α^n    (n≥0).  The values of A and B are uniquely  determined by the values of a_1  and a_0 .

$${Let}\:{t},{r},{c}\:{be}\:{constants},\:{t}\neq\mathrm{0},\:{in}\:{the} \\ $$$${recurrence}\:{relation}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:{ta}_{{n}+\mathrm{1}} +{ra}_{{n}} +{ca}_{{n}−\mathrm{1}} =\mathrm{0}\:\:\:\:\left({n}\geqslant\mathrm{1}\right) \\ $$$${defining}\:{the}\:{sequence}\:\left\{{a}_{{n}} \right\}\:{with}\: \\ $$$${a}_{\mathrm{0}} ={f}\:{and}\:{a}_{\mathrm{1}} ={h}. \\ $$$${Consider}\:{the}\:{auxiliary}\:{equation}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:{t}\lambda^{\mathrm{2}} +{r}\lambda+{c}=\mathrm{0} \\ $$$${whose}\:{roots}\:{are}\:\alpha\:{and}\:\beta. \\ $$$${The}\:{general}\:{term}\:{a}_{{n}} \:{of}\:{the}\:{sequence} \\ $$$${is}\:{then}\:{given}\:{by}\: \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:{a}_{{n}} ={A}\alpha^{{n}} +{B}\beta^{{n}} \:\:\left({n}\geqslant\mathrm{0}\right) \\ $$$${if}\:\alpha\neq\beta. \\ $$$${If}\:\:\alpha=\beta\neq\mathrm{0},\:{a}_{{n}} =\left({An}+{B}\right)\alpha^{{n}} \:\:\:\left({n}\geqslant\mathrm{0}\right). \\ $$$${The}\:{values}\:{of}\:{A}\:{and}\:{B}\:{are}\:{uniquely} \\ $$$${determined}\:{by}\:{the}\:{values}\:{of}\:{a}_{\mathrm{1}} \:{and}\:{a}_{\mathrm{0}} . \\ $$$$ \\ $$

Commented by Yozzii last updated on 17/Dec/15

Can′t p^2 +4q<0 ?

$${Can}'{t}\:{p}^{\mathrm{2}} +\mathrm{4}{q}<\mathrm{0}\:? \\ $$

Commented by prakash jain last updated on 17/Dec/15

p^2 +4q can be less than 0 real or complex.  I just solved for one case >0.  As you mentioned if p^2 +4q=0, both roots  are equal say r  a_n =k_1 r^n +k_2 nr^n   for unequal roots previous result is correct.

$${p}^{\mathrm{2}} +\mathrm{4}{q}\:\mathrm{can}\:\mathrm{be}\:\mathrm{less}\:\mathrm{than}\:\mathrm{0}\:{real}\:{or}\:{complex}. \\ $$$${I}\:\mathrm{just}\:\mathrm{solved}\:\mathrm{for}\:\mathrm{one}\:\mathrm{case}\:>\mathrm{0}. \\ $$$$\mathrm{As}\:\mathrm{you}\:\mathrm{mentioned}\:\mathrm{if}\:{p}^{\mathrm{2}} +\mathrm{4}{q}=\mathrm{0},\:\mathrm{both}\:\mathrm{roots} \\ $$$$\mathrm{are}\:\mathrm{equal}\:\mathrm{say}\:{r} \\ $$$${a}_{{n}} ={k}_{\mathrm{1}} {r}^{{n}} +{k}_{\mathrm{2}} {nr}^{{n}} \\ $$$${for}\:{unequal}\:{roots}\:{previous}\:{result}\:{is}\:{correct}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com