Please help me solve this one. I need your help. I have attached the lecture slides too just in case. HELP ME PLEASE Solve the recurrence relationif n = 0if n = 1 ): N → Ra :=n H{1(5аn-1 — бап-2 + 4п, ifn > 1, Suppose (a)nen is a homogeneous, linear recurrence relation of order (k + 1)whose characteristic equation has all real roots where å,, A2.. ,A, are its distinctroots with multiplicities m1, m2 , m, respectively (for some / e 1..k). Thenm, + m2 + + m, -k+1 and the solution to the recurrence relation has theformEx:Thm:Topic 2.6.0: Recurrence RelationsTopic 2.6.2: Homogeneous Solutions1)A Geometric Progression, GP(y.r, a)3)The Tower of Hanoi Sequence, if n = 0yy= (n- Ya-z if n >ifn =):N-RSuppose k eN. A sequence function of the form:- Hn-1 + 1, ifn>Suppose k EN and a is a homogeneous, linear recurrence relation of order (k + 1):Def:Def:P(n) = Pa, (n) + Pa, (n) + + Pa, (n)--E. ifn= 0, if n = 1y is a homogenous, linear recurrencerelation or order 1.His a non-homogenous, linearIfn = 0ifn = 1recurrence relation of order 1:N -Rwith appropriate values of the undetermined coefficients in the partial solutions.The values of the undetermined coefficients can be found by solving the linearsystem::N-R. ifn=kifn=k(@n-k+1. -1. n), ifn>k2) The Fibonacci Sequence4) The factorial functionand A, 22, Ag+1 are all of its characteristic roots (counting multiplicity). We say that therecurrence relation is solvable in Rif vj € 1.. (k + 1), 2, ER (that is, all characteristicroots are real).(P(0) = a,P(1) =is called a recurrence relation of order (k + 1) with initial conditions ag, a, a. ifn = 0. ifn =ifn =O = (n-: (n – D. itn > 0):N - RIf there exist ca.C..C ER and o E Fnc(N, R) such that-N:Suppose a homogenous, linear recurrence relation has de as a characteristic root withmultiplicity m. Then the partial solution contributed by do is the expressionDef:(an-k, an-k+1an-1,n) = Coan-k-1 + an-k ++ Cgan-1 + (n).Fis a homogeneous, linear recurrencerelation of order 2.The factorial is a homogeneous, non-linear recurrence relation of order 1.The solution to the recurrence relation will be a = (n- p(n)) for the determinedcoefficients.P2, (n) = b1(4.)" + b,2(n)(de)" + -.+ bm(n™-1)(4,)"then the recurrence relation is linear (otherwise it is non-linear). If (n) = 0, then therecurrence relation is homogeneous (otherwise it is non-homogenous). If o 0, it iscalled the non-homogeneous component of the recurrence relation.Once a solution is determined, one must show that it actually solves therecurrence relation (which may require an inductive proof).Rmk:We will not address non-linear recurrence relations in this course.where b1, b2... , bm are undetermined real constants.Rmk:Rmk:Ex:From the previous examples:Ex:2) For F, its characteristic equation is 2? =2 + 1. This leads to two rootsTopic 2.6.1: Characteristic EquationsThe order of the resulting polynomial equation will have the same order as therecurrence relation.1) For y, its characteristic root is the constant r (which is real). This means thatp(n) = b- (r)" for some undetermined coefficient b. We know though that a, = a1+ V521- V5Ex:The general homogeneous equations and the resulting characteristic equations forthe first three recurrence relation examples given earlier are:soDef:Suppose k eN and a is a linear recurrence relation of order (k + 1):So p(n) is of the form b, (E) + b ( for undetermined coefficients b,and bz. Examining the initial conditions gives:ifn = 0y. ifn = 11) Ya =r Yn-1b = a:N-RF(0) = 0F(1) = 1.ifn klCoan-k-1 + Can-k++ Ckan-1 +9(n), ifn >k/2) F = Fa-1+ F-2 =2" = A"-1+ A"-222 =+1Thus a = (n a(r)").+ b2Check:Then the general homogeneous equation is:b + bz =03) H, = 2- Hn-12" - 21-12- 2p(0)(n €N) (P(n) =r•p(n – 1))bz - -bb, V5 = 1an = Coan-k-1 +can-k + + Cgan-1-= a(r)= a(1)P(n + 1)- a(r)"+1= (r) · a(r)"Def:If 2o is a root of the characteristic equation, it is called a characteristic root of therecurrence relation. If 2, has a multiplicity higher than 1, it is called a repeatedThis leads to b; =and b2 = -%3DReplacing each instance of a, with a-(n-k-1) gives rise to the correspondingcharacteristic equation for the recurrence relation:root.= aWe will focus only on recurrence relations whose roots are real.p(0) = YoVn €Z*, (Y = P(n))Hence, Vn E N, F(n) = ()-Rmk:(which still needs to be checked).Thm:Consider the non-homogeneous, linear recurrence relation:Given a non-homogeneous linear recurrence relation a with non-homogeneouscomponent o, if o is of the form in the left column, then the push solution is of theform in the right column (in the same row) with the indicated undeterminedcoefficients.Ex:Ex (cont.): This leads to B, = -.B,=. Examining the initial conditions gives:Topic 2.6.3: Non-Homogeneous Solutions, ifn =B(2) = 1B = (n-e-1 +n– 1, ifn > 2): (2.) -RSuppose k €Nand a is a non-homogeneous, linear recurrence relation of order(k + 1):Def:(C, Ag.Az.Az, - are given constants while K, Bg, Bq, B2, --. are undeterminedconstants)Its characteristic equation is à = 1 (which clearly has exactly one root) and has asolution form p(n) = b for some constant b. Since the non-homogeneouscomponent is p(n) = n- 1, then the push solution is of the form (n) = B,n +B, where B, and Bị are an undetermined constants. The constant term is the sameformat as the general solution so we need to multiply (n) by the least power of nfor which there is no longer a part in the general solution form. This means thatV(n) - Bon + B,n? will be the push solution and the solution is of the form1+b=1ifn= 0.ifn=1--E(n)(n)b= 0.:N-R.ifn=kC, a constantK (an undetermined constant)Hence B(n) = n² -n for n 22.Coan-k-1+ cam-k ++ Can-1 + (n).ifn>kA,nB,(n) + B_0B(n) = b+ Bon + B,n?.A (n™) for m ENC(t)" for t €ZAm(n™)(t)" for m eN, t €ZBo + B, (n) + -- + Bm(n™)The previous example arises from the "handshaking problem." The functionB counts how many handshakes are necessary for a group of n people to haveshaken hands with each other person exactly once. This could have also beensolved by realizing that the answer is the same as determining how many subsetsof size 2 can be formed from a set of size n.Rmk:We say that y: N - Ris a push solution to the recurrence relation if it is a solutionto the relation but does not include a part that is a solution to the correspondinghomogeneous linear recurrence relation. If p: N+ R is the undetermined solution tothe general homogeneous relation then p(n) + p(n) is the specific solution to thenon-homogeneous relation.K(m)"Substituting (n) = Bạn + Bạn? into the recurrence relation gives:(t)"(B, + B, (n) + -…· + B„(n™))(n) = v(n – 1) + n - 1(B,n + B,n) = (B,(n – 1) + B, (n –- 1)2) + n – 1Bon + B,n = Bon - B, + B,n? - 2B,n + B, +n-10 = (1- 28, )n + (B, – B, – 1).Rmk:The push solution can be solved through the recurrence relation by eliminatingundetermined coefficients.Suppose v(S) = n. v(P:(5)) = C(n.2) = "le=1)7= B(n).Rmk:The task then is to find the push solution and use the general solution from thecorresponding homogeneous relation.1Ex:Ex (cont): This means that H(n) = b(2)" - 1 for some b. We examine the initial conditionWe saw that Hwas a non-homogeneous recurrence relation with non-homogeneous component (n) = 1. The single characteristic root was 2. So thegeneral solution has the form:H(1) -1p(n) = b(2)".b(2) -1-12b -1=1Since o is a constant, then the push solution will also be a constant, K. This is not apart of the general solution so we do not need to adjust y.2b = 2So the solution has the formb = 1H(n) = b(2)" + KHence, H(n) = (2)" –1.Check:for undetermined coefficients b and K. Substituting (n) = K into the recurrencerelation we get:(nE N) (H(n) = 2 - H(n – 1) + 1)H(n + 1)= (2)*+1-1= 2(2") – 2+1= 2(2" - 1) + 1= 2- H(n) +1H(n) = 2 - H(n – 1) +1H(1)(n) = 2 - p(n – 1) +1= (2) -1=2-1= 1(K) = 2(K) +1= HeH(0) = H.K = -1

Name: Please help me solve this one. I need your help. I have attached the l
Uploaded: 2024-03-20T07:07:37.000Z
Channel: Bartleby
Description: Please help me solve this one. I need your help. I have attached the lecture slides too just in case. HELP ME PLEASE Solve the recurrence relationif n = 0if n = 1 ): N → Ra :=n H{1(5аn-1 — бап-2 + 4п, ifn > 1, Suppose (a)nen is a homogeneous, linear