# Back Substitution

```Back subsitution can be used to come up with a formula for some of the
simpler recurrence relations.  Here is a brief explanation and example:

Let me write a(n) in place of a sub n, as I can't get subscripts
in plain text!  Back substitution starts with the recurrence relation
for a(n).  You then substitute in a similar expression for a(n-1),
a(n-2), or whichever of the a's occur in the expression for a(n).
Then you substitute again and again, until you can see a pattern
that takes you all the way down to a(1) or other simple cases where
a number answer is directly known from the initial conditions.
In some cases the pattern is easy to see, in others it is difficult.

One example from class went like this:
We had a recurrence:  a(n) = n * a(n-1)
with initial condition:  a(0) = 1

Back substitution starts with a(n) = n * a(n-1)
Then we substitute for a(n-1) on the right hand side the expression
given for a(n-1) by the recurrence.  This would have to be
a(n-1) = (n-1) * a(n-2), where we have replaced n by n-1 everywhere
n occurred in the original recurrence relation.
So, after the substitution we get:
a(n) = n * a(n-1)
= n * (n-1) * a(n-2)
Then we substitute into the right hand side of that one an expression
for a(n-2), namely a(n-2) = (n-2) * a(n-3)
At this point we have:
a(n) = n * a(n-1)
= n * (n-1) * a(n-2)
= n * (n-1) * (n-2) * a(n-3)
We begin to see the pattern here and just continue it by writing:
a(n) = n * (n-1) * (n-2) * ... * 3 * 2 * a(1)
Note that we stopped with a(n - (n-1)), which is a(1).  This fits
our pattern since it had the value inside a() one less than the
last factor before the a().
Since a(1) = 1 by the initial condition, we get:
a(n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1 = n!
```