Recurrence Relations

A recurrence relation is an equation in which each term of the sequence is defined as a function of the preceding terms.

There are different ways of solving these relations, we're going to examine:

1. repeated derivation/substitution
2. telescoping

Solving recurrence relations by repeated derivation/substitution

The premise for this type of solution is to continually substitute the recurrence relation on the right hand side (ie. substitute a value into the original equation and then derive a previous version of the equation). The various derivations should lead to a generalized form of the equation that can be solved for a time constraint on the algorithm/equation: For example:

T(n) = T(n/2) + c

The only substitution available at this point is to substitute n/2 for n in the original equation:

T(n/2) = T(n/2/2) + c
T(n/2) = T(n/4) + c

Add c to both sides to derive the original equation:

T(n/2) + c = T(n/4) + c + c

Therefore:

T(n)  =  T(n/2) + c  =  T(n/4) + c + c

Now that another equation has been derived there is a new substitution that can be made in the original: n/4 for n

T(n/4) = T(n/4/2) + c
T(n/4) = T(n/8) + c

T(n/4) + c + c = T(n/8) + c + c + c

T(n)  =  T(n/2) + c  =  T(n/4) + c + c  =  T(n/8) + c + c + c

In general, the basic equation is:

T(n)  =  T(n/2k) + kc    for k > 0

Making an assumption that n = 2^k allows for:

T(n) = T(n/2k) + kc

T(n) = T(n/n) + (log n) * c
T(n) = T(1) + c log n

T(n) = b + c log n

T(n) = O(log n)

Solving recurrence relations by telescoping

The premise for this type of solution is to substitute values for n, add up the results, and eliminate like terms. For example:

T(n) = T(n/2) + c

T(n/2)  =  T(n/4) + c
T(n/4)  =  T(n/8) + c
T(n/8)  =  T(n/16) + c
...
T(n/2k-1)    =  T(n/2k) + c


T(n) + T(n/2) + T(n/4) + T(n/8) + ... + T(2) = T(n/2) + c + T(n/4) + c + T(n/8) + c + T(n/16) + c + ... + T(2k) + c


T(n) = T(n/2k) + kc

Making an assumption that n = 2^k allows for:

T(n) = T(n/2k) + kc

T(n) = T(n/n) + (log n) * c
T(n) = T(1) + c log n

T(n) = b + c log n

T(n)  =  O(log n)

Some Useful Series

The Basic Series:

S(n) = 1 + 2 + 3 + 4 + ... + n

       n
     = ∑ i
      i=1
      
     = n( 1 + n )
           2

Sum of Squares:

       n
S(n) = ∑ i2
      i=1
      
     = n(n + 1)(2n1 + 1)
              6
      
     ≈ n3   for large n
       3

Sum of Exponents:

       n
S(n) = ∑ ik
      i=1
      
        nk+1
     = _____     for large n  and k ≠ -1
       |k+1|

Geometric Series:

       n
S(n) = ∑ Ai
      i=0
      
        An+1 - 1
     = ---------
         A - 1

Special Case: A = 2 results in  2n+1 - 1

Solve the following recurrence relation

You may assume that n = 2^k:

T(1) = 1
T(n) = 2T(n/2) + n