Question

8. Suppose that r" and q” are both solutions to a recurrence relation of the form an = aan-1+ Ban-2. Prove that c.pn + d.g” is also a solution to the recurrence relation, for any constants c, d.

Answer 1

Given that on and an are both solution to the recurrence relation of the form an= a ani + Baner - So, q=on sectisfies 0. gn=ar + Brna & Br tr"-army-prn2 = 0 again an- & also satisfies & 4 = &qu l + p q n.2 - aqul - p q r2 = 0

Now to check ern+do que also satisfied or not for any constec, d Let us assume an= cign + diqn j N σω an- xani-ß an-z = (c.rn+d. q) & (c.rn + d. q-1) 1 .-p Ccionatd.qn-2) = c.r_gc.on-1 Born-2 I dgn - xd.qon-1 - B dqn-2 - c [r"-xr1 Brn-2] ++ [9"-aquat-pq"-] = 0+ 0 [ by © and m]

Hence an=crn+d.qna satisfieg equ" o so, con + c. qu is also solution to the recurrenee relation for any constants. cod.