B tech. Discrete mathematics (I. T & Comp. Science Engg.) Syllabus

METHODS OF SOLVING RECURRENCE RELATION :
Now, in this section we shall discuss a few methods of solving recurrence relation and hence solve the relations that we have formulated in the previous section.
Backtracking Method:
This is the most intuitive way of solving a recurrence relation. In this method, we substitute for every term in the sequence in the form of previous term (i.e. a_n in the form of a_n–1, a_n–1 in the form of a_n–2 and so on) till we reach the initial condition and then substitute for the initial condition. To understand this better, we shall solve the recurrence relations that we have come across earlier.
Example: Solve the recurrence relation a_n = 1.06a_n–1, with a₀ = 0.5.
Solution: Given recurrence relation is a_n = 1.06a_n–1, with a₀ = 0.5. From this equation, we have a_n = 1.06a_n–1 = 1.061.06 a_n–2 = 1.061.061.06 ^an–³ Proceeding this way, we have a_n = (1.06)ⁿa₀. But, we know that a₀ = 0.5.<sup>Thus, explicit solution to the given recurrence relation is an =

0.5(1.06)n</sup>for n  0.