Forward Substitution
Forward substitution
Let’s consider the recurrence
 T(n) = T(n1) + 2n – 1
 T(0) = 0
The method of forward substitution proceeds by generating the first halfdozen or so terms in the sequence described by the recurrence, in the hope that it will turn out to be a sequence we recognize. In this case, we can calculate

n
T(n)
0
0
1
1
2
4
3
9
4
16
5
25
and at this point we can shout “Aha! This example was carefully rigged to give T(n)=n²!”. Unfortunately, there are infinitely many sequences that start with these six numbers, so we can’t be fully sure that this is the right answer until we prove it. So let’s do so.
We will show that T(n) = n² satisfies the above recurrence for all n, by induction on n. The base case is n = 0; here T(0) = 0 = 0². For n > 0, we have
 T(n) = T(n1) + 2n – 1 = (n1)² + 2n – 1 = n² – 2n + 1 + 2n – 1 = n²,
and we are done.
(Here we used the induction hypothesis where we replace T(n1) by (n1)². We will usually not be very explicit about this.)
Here’s a less rigged example:
 T(n) = T(floor(n/2)) + n, T(0) = 0.
Computing small cases gives

n
T(n)
0
0
1
1
2
3
3
4
4
7
5
8
6
10
7
11
8
15
which doesn’t really tell us much about the behavior for large values. We can easily add a few powers of 2 to get an idea of what happens later:

16
31
32
63
64
127
From this we might guess that the solution satisfies T(n) <= 2n (or perhaps T(n) <= 2n – 1 for n > 0). So let’s see if we can prove it:
 Base case

T(0) = 0 <= 2n.
 Induction step

For n > 0, T(n) = T(floor(n/2) + n <= 2 floor(n/2) + n <= 2(n/2) + n = 2n.
We might be able to prove a slightly tighter bound with more work, but this is enough to sho T(n) = O(n). Showing that T(n) = Omega(n) is trivial (since T(n) >= n), so we get T(n) = Θ(n) and we are done.
Applying the method of forward substitution requires a talent for recognizing sequences from their first few elements. If you are not born with this talent, you can borrow it from the mathematician Neal J. A. Sloane, or at least from his online