hi Tell whether or not each reccurrence relation below is a linear homogeneous r

Question

hi

Tell whether or not each reccurrence relation below is a linear homogeneous recurrence relation with constant coefficients. If it isn't, say why. If it is, say what order it is. an = 41an-1 -root 2an-2 bn = 8bn-1 + 3 Cn = 6cn-1 + 2nCn-2 Solve the following recurrence relation, with the given initial conditions an = 9an-1 + 36an-2; a0 = 5, a1 = 0 Solve the following recurrence relation, with the given initial conditions. an = 20an-1 - 100an-2; ao = 3, a1 = 10 Consider the reccurrence relation bn = b[n/2] + b[(n+1)/2] + 2 for n >1 with initial condition b1 = 0. Solve the recurrence in the case that n is a power of 2 to obtain bn = 2n - 2.

Explanation / Answer

(a) an=41an?1?2?an?2is a linear homogeneous reccurence relation with constant coefficient of order 2    (b)     bn=8bn?1+3 is not homogeneous as there is a constant term 3  

(c)     cn=6cn?1+2ncn?2 is not with constant coefficient as 2n is a coefficient of cn?2  

HW6-5: The recurrence relation is     an=9an?1+36an?2,a0=5,a1=0.  

    the reccurence is x2?9x?36=0 and its roots are -12 and 3.  

    the recurrence is an=?(?12)n+?3n,n?0  

initial conditions: a0=?+?=5 and a1=?12?+3?=0  

we have ?=1 and ?=4  

the recurrence is an=(?12)n+4.3n,n?0  

HW6-6:      an=20an?1?100an?2,a0=3,a1=10  

    the reccurence is x2?20x+100=0 and it has a twice repeated root 10.  

    the recurrence is an=(?+?n)10n,n?0  

conditions: a0=?+?.0=?=3 and a1=(?+?).10=10  

we have ?=3 and ?=?2  

the recurrence is an=(3?2n)10n,n?0  

HW6-7:     the recurrence relation is bn=b?n/2?+b?(n+1)/2?+2,b1=0.  

   When n is a power of 2 and n > 1, then b?n/2?=b?(n+1)/2?=bn/2  

   So, for n power of 2 and n > 1, the recurrence turns to bn=2bn/2+2  

     So, if we solve iteratively, we have  

   bn=2bn/2+2=2(2bn/4+2)=4bn/4+4+2=8bn/8+8+4+2=?=nb1+n+n/2+n/4+?+4+2       =2(n/2+n/4+?+2+1)=n2(n2+1)=n(n+2)4   

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.