Recursive Relations

We developed two algorithms, one iterative and one recursive, to compute a value $S(n)$ for the sequence S of Example 1. However, there is still easier way to compute $S(n)$. Recall that:

$ S(1) = 2 $ (1)
$ S(n) = 2S(n-1) $ for $n$ ≥ 2 (2)

Because

$S(1) = 2 = 2^1 $
$S(2) = 4 = 2^2 $
$S(3) = 8 = 2^3 $
$S(4) = 16 = 2^4 $

and so on, we can see that

$S(n) = 2^n $ (3)

Using Equation (3), we can plug in a value for $n$ and compute $S(n)$ without having to compute -- either explicitly, or, through recursion, implicitly -- all the lower values of $S$ first. An equation such as (3), where we can substitute a value and get the output value back directly, is called a closed-form solution to the recurrence relation (2) subject to the basis step (1). Finding a closed-form solution is called solving the recurrence relation. Clearly, it is nice to find a closed-form solution to a recurrence relation whenever possible.

Linear First-Order Recurrence Relations

Expand, Guess, and Verify

One technique for solving recurrence relations is an "expand, guess, and verify" approach that repeatedly uses the recurrence relation to expand the expression for the $n_{th}$ term until the general pattern can be guessed. Finally the guess is verified by mathematical induction.

Example 1:

Consider again the basis step and recurrence relation for the sequence $S$ of Example 1:

S(1) = 2 (4)
S(n) = 2S(n-1) for n >= 2 (5)

Let's pretend we don't already konw the closed-form solution and use the expand, guess, and verify approach to find it. Beginning with $S(n)$, we expand by using the recurrence relation repeatedly. Keep in mind tha the recurrence relation is a recipe that says S at any value can be replaced by two times S at the previous value. We apply this recipe to S at the values $n, n-1, n-2$,and so on.

 
S(n) = 2S(n-1)
     = 2[2S(n-2)] = 2²S(n-2)
     = 2²[2S(n-3)] = 2³S(n-3)

By looking at the developing pattern, we guess that after $k$ such expansions, the equation has the form

     S(n) = 2^kS(n-k)

This expansion of S values in terms of lower S values must stop when $n-k = 1$, that is, when $k = n - 1$. At that point,

    S(n) = 2^n-1S[n - (n-1)]
         = 2^n-1S(1) = 2^n-1(2) = 2ⁿ

which expresses the closed-form solution.

We are not done yet, however, because we guessed at the general pattern. We now confirm our closed-form solution by induction on the value of $n$. The statement we want to prove is therefore $S(n) = 2^n$ for $ n ≥ 1 $.

For the basis step, $S(1) = 2$. This is true by equation (4). We assume that $S(k) = 2^k $. Then

S(k+1) = 2S(k)       (by equation (5))
       = 2(2^k)       (by the inductive hypothesis)
       = 2^k+1

This proves that our closed-form solution is correct.

A Solution Formula

Some types of recurrence relations have known solution formulas. A recurrence relation for a sequence $S(n)$ is linear if the ealier values of S appearing in the definition occur only to the first power. The most general linear recurrence relation has the form:

$ S(n)= f_1(n)S(n-1) + f_2(n)S(n-2) + \dots + f_k(n)S(n-k) + g(n) $

, where the $f_i's$ and $g$ can be expressions involving $n$. The recurrence relation has constatn coefficients is the $f_i's$ are all constants. It is first-order if the $n_{th}$ term depends only on term $n-1$. Linear first-order recurrence relations with constant coefficients therefore have the form:

$S(n) = cS(n-1) + g(n) $ (6)
Finally, a recurrence relation is homogeneous if $g(n) = 0$ for all $n$.
We will find the solution formula for equation (6), the general linear first-order recurrence relation with constant coefficients, subject to the basis that $ S(1) $ is known. We will use the expand, guess, and verify approach. Repeatedly applying equation (6) and simplifying, we get:

S(n) = cS(n-1) + g(n)
     = c[cS(n-2) + g(n-1)] + g(n)
     = c²S(n-2) + cg(n-1) + g(n)
     = c²[cS(n-3) + g(n-2)] + cg(n-1) + g(n)
     = c³S(n-3) + c²g(n-2) + cg(n-1) + g(n)
                         ⋮

After $k$ expansions, the general form appears to be

$ S(n) = c^kS(n-k) + c^{k-1}g(n-(k-1)) + \dots + cg(n-1) + g(n) $

If the sequence has a base value at 1, then the expansion terminates when n-k=1 or k = n-1, at which point:

S(n) = c^n-1S(1) + c^n-2g(2) + … + cg(n-1) + g(n)
     = c^n-1S(1) + c^n-2g(2) + … + c¹g(n-1) + c⁰g(n)                (7)

We can use summation notation to write part of this expression more compactly. The uppercase Greek letter sigma, Σ, stands for summation. In summation notation, Equation (7) becomes Equation (8):

$$ S(n) = c^{n-1}S(1) + \sum_{i=2}^{n}c^{n-i}g(i) \quad (8)$$ Therefore, the solution to the recurrence relation (6) is Equation (8)

Table 1: Steps of Solution formula
1. Match your recurrence relation to the form: S(n) = cS(n-1) + g(n) to find c and g(n)
2. Use c, g(n), and S(1) in the formula $$S(n) = c^{n-1}S(1) + \sum_{i=2}^nc^{n-i}g(i) $$
3. Evaluate the resulting summation to get the final expression.

Example 1:

The sequence S(n) of example 1,
         S(1) = 2
         S(n) = 2S(n-1) for n >= 2
is a linear, first-order, homogeneous recurrence relation with constant coefficients. 
In other words, it matches equation (6) with c = 2 and g(n) = 0. Because g(n) = 0,
the g function evaluates to 0 no matter what the argument is. From formula (8),
the closed-form solution is:

$$ S(n) = 2^{n-1}(2) + \sum_{i=2}^{n}0 = 2^n $$

which agress with our previous result.

Example 2:

Find the closed-form solution to the recurrence relation:
         T(1) = 1
         T(n) = T(n-1) + 3 for n >= 2
This is a linear, first-order recurrence relation with constant coefficients. 
In other words, it matches equation (6) with c = 1 and g(n) = 3.
From formula (8), the closed-form solution is:

$$ S(n) = 1^{n-1}(1) + \sum_{i=2}^{n}1^{n-i}*3 = 1 + \sum_{i=2}^{n}3 = 1 + 3*(n-1) = 3n -2 $$

Example 3:

Find the closed-form solution to the recurrence relation:
         S(1) = 1
         S(n) = S(n-1) + n for n >= 2
This is a linear, first-order recurrence relation with constant coefficients. 
In other words, it matches equation (6) with c = 1 and g(n) = n.
From formula (8), the closed-form solution is:

$$ S(n) = 1^{n-1}(1) + \sum_{i=2}^{n}1^{n-i}*i = 1 + \sum_{i=2}^{n}i = \sum_{i=1}^{n}i = \frac{n(n+1)}{2} $$

What is Linear, First Order, Constant Coefficient

(1) If the S(n-1) term is not to the first power, then it isn't Linear.
For example: S(n) = S(n-1)² for n > 1; This one has S(n-1) to the second power, so it isn't Linear. Therefore we cannot use equation (8).

(2) If it has more previous terms than just the n-1 term then it isn't First Order.
For example: F(n) = F(n-1) + F(n-2) for n > 2; This one has F(n-1) and F(n-2), so it isn't First Order. Therefore we cannot use equation (8).

(3)If the coefficient of the n-1 term has an n in it (for example, n or 2ⁿ), then it isn't Constant Coefficient.
For example: S(n) = n*S(n-1) for n > 1; This one has n as the coefficient,so it isn't Constant Coefficient. Therefore we cannot use equation (8).

Practice

(1) Find a closed-form solution to the recurrence relation:

	
	S(1) = 4
	S(n) = 2S(n-1) + 3 for n >= 2

Hint: $1 + 2^1 + 2^2 + \dots + 2^n = 2^{n+1} - 1$

With the general form $ S(n) = cS(n-1) + g(n) $, we see that: $ c= 2, g(n) = 3 $
Substituting into the general solution form:

$$ S(n) = c^{n-1}S(1) + \sum_{i=2}^nc^{n-i}g(i) $$
we get:

$$ \begin{aligned} S(n) & = 2^{n-1}(4) + \sum_{i=2}^n2^{n-i}(3) \\ & = 2^{n-1}(2^2) + 3\sum_{i=2}^n2^{n-i} \\ & = 2^{n+1} + 3[2^{n-2} + 2^{n-3} + \dots + 2^1 + 2^0] \\ & = 2^{n+1} + 3[2^{n-1} - 1] \end{aligned} $$

(2) Find a closed-form solution to the recurrence relation:

	
	T(1) = 2
	T(n) = T(n-1) + (n+1) for n >= 2

Hint: $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$

Reference

saylor academy