Recurrences centuries.)A linear recurrence has the form: f(n)=a1f(n-1)+a2f(m-2)+…+af(n-d) ∑bf(n-) where a1, a2,. ad are constants. The order of the recurrence is d. For example, the Fi bonacci recurrence is order 2 and has coefficients a1 a2=1.(Later on, we'll slightly expand the definition of a linear recurrence. For now, let's try to solve just the Fibonacci recurrence; well see how to solve general linear recurrences later in the lecture. Our rule of thumb is that guess-and-verify is the first method to apply to an unfamiliar recurrence. It turns out that for a linear recurrence, an exponential solution is a good guess. However, since we know nothing beyond this, our initial guess-and-erify attempt will really only be a"dry run"; that is, we will not make an exact guess and will not verify it with a complete proof. Rather, the goal of thi first attempt is only to clarify the form of the solution Guess. f(n)=ca" Here c and r are parameters introduced to improve our odds of having a correct guess, n the verification step, we can pick values that make the proof work. To further improve odds, let's neglect the boundary cond f(0)=0andf(1)=1 verification. Plugging our guess into the recurrence f(n)=f(n-1)+f(n-2) gives x2=x+1 l=0 1士√5 In the first step, we divide both sides of the equation by crn-. Then we rearrange terms and find a with the quadratic formula This calculation suggests that the constant c can be anything but that r must be (1±√⑤)/2. Evidently, there are two solutions to the recurrence: f(n) 1+√5 In fact, any linear combination of these two solutions is also a solution. The following theorem states that this is true in general for linear recurrences Theorem 1. If f(n)and g(n) are solutions to a linear recurrence(without boundary conditions), then cf(n)+ dg(n) is also a solution� Recurrences 7 centuries.) A linear recurrence has the form: f(n) = a1f(n − 1) + a2f(n − 2) + . . . + adf(n − d) d = bif(n − i) i=1 where a1, a2, . . . ad are constants. The order of the recurrence is d. For example, the Fi￾bonacci recurrence is order 2 and has coefficients a1 = a2 = 1. (Later on, we’ll slightly expand the definition of a linear recurrence.) For now, let’s try to solve just the Fibonacci recurrence; we’ll see how to solve general linear recurrences later in the lecture. Our rule of thumb is that guess­and­verify is the first method to apply to an unfamiliar recurrence. It turns out that for a linear recurrence, an exponential solution is a good guess. However, since we know nothing beyond this, our initial guess­and­erify attempt will really only be a “dry run”; that is, we will not make an exact guess and will not verify it with a complete proof. Rather, the goal of this first attempt is only to clarify the form of the solution. Guess. n f(n) = cx Here c and x are parameters introduced to improve our odds of having a correct guess; in the verification step, we can pick values that make the proof work. To further improve our odds, let’s neglect the boundary conditions, f(0) = 0 and f(1) = 1. Verification. Plugging our guess into the recurrence f(n) = f(n − 1) + f(n − 2) gives: n n−1 cx = cx + cx n−2 2 x = x + 1 2 x − x − 1 = 0 1 ± √5 x = 2 In the first step, we divide both sides of the equation by cxn−2. Then we rearrange terms and find x with the quadratic formula. This calculation suggests that the connstant c can be anything, but that x must be (1 ± √5)/2. Evidently, there are two solutions to the recurrence: � � 1 − √5 n �n 1 + √5 � f(n) = c or f(n) = c 2 2 In fact, any linear combination of these two solutions is also a solution. The following theorem states that this is true in general for linear recurrences. Theorem 1. If f(n) and g(n) are solutions to a linear recurrence (without boundary conditions), then cf (n) + dg(n) is also a solution