FIND INFINITE SUM OF RECURSIVE SEQUENCE HOW TO
(See ComputingSums for how to compute this sum.) This is the same guess that we got from the method of forward substitution, so we prove that it works in the same way. įrom this we might reasonably guess that T(n) is bounded by Sloane, or at least from his on-line Encyclopedia of Integer Sequences.īackward substitution, like forward substitution, tries to find a pattern from which we can guess a solution that we then prove using other techniques-but now we start with T(n) and expand it recursively using the recurrence.įor example, if we consider the same T(n) = T(n/2) + n recurrence from above, and assume for simplicity that n is a power of 2, then we get If you are not born with this talent, you can borrow it from the mathematician Neal J. T(0) = 0 0, T(n) = T(floor(n/2) + n = n), so we get T(n) = Θ(n) and we are done.Īpplying the method of forward substitution requires a talent for recognizing sequences from their first few elements. So let's see if we can prove it: Base case In this case, we can calculateįrom this we might guess that the solution satisfies T(n) 0).
The method of forward substitution proceeds by generating the first half-dozen or so terms in the sequence described by the recurrence, in the hope that it will turn out to be a sequence we recognize. But sometimes it is possible to make a good guess by iterating the recurrence a few times and seeing what happens. Naturally, unless you are very good friends with the existential quantifier you may find it had to come up with good guesses. So the most general method for solving recurrences can be called "guess but verify". 1 From this point on we will assume that we only consider values of n for which the recurrence relation does not produce any non-integer intermediate values.Īs when solving any other mathematical problem, we are not required to explain where our solution came from as long as we can prove that it is correct. If we want an exact solution for values of n that are not powers of 2, then we have to be precise about this, but if we only care about a big-Theta solution we will usually get the same answer no matter how we do the rounding. big-Theta) solution (see AsymptoticNotation).īy convention we only define T by a recurrence like this for integer arguments, so the T(n/2) by convention represents either T(floor(n/2)) or T(ceiling(n/2)).
Not all recurrences are solvable exactly, but in most of the cases that arises in analyzing recursive algorithms, we can usually get at least an asymptotic (i.e. To solve a recurrence, we will find a formula that calculates T(n) directly from n, without this recursive computation. In principle such a relation allows us to calculate T(n) for any n by applying the first equation until we reach the base case. These are originally from CS365, and emphasize asymptotic solutions for CS202 we recommend also looking at GeneratingFunctions.Ī recurrence or recurrence relation defines an infinite sequence by describing how to calculate the n-th element of the sequence given the values of smaller elements, as in: Wolfram Knowledgebase Curated computable knowledge powering Wolfram|Alpha.Notes on solving recurrences. Wolfram Universal Deployment System Instant deployment across cloud, desktop, mobile, and more. Wolfram Data Framework Semantic framework for real-world data.
0 kommentar(er)
