1 Use mathematical induction to prove that the Tn 2n 1 is

1. Use mathematical induction to prove that the Tn = 2n – 1 is a closed form for the following recurrence relation:

Tn = 2Tn-1 + 1,
T0 = 0

Solution

T_n = 2ⁿ - 1 satisfies the recurrence: T₀ = 0,

                                                           T₁ = 1

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

The proof is done by induction on n. The induction hypothesis is that T_n = 2ⁿ -1. This is true for n = 1 because T₁ = 1 = 2¹ -1. Now assume that T_n-1 = 2 ^n-1 - 1 in order to prove that T_n = 2ⁿ - 1, where n >= 2:

      T_n = 2T_n-1 + 1

           =    2(2^n-1 -1) +1

            =    2ⁿ – 1

The first equality is the recurrence equation, the second follows from the induction assumption, and the last step is simplification

“Expansion” or “Iteration” is another way to solve recurrences.

The method consists of three steps:

Step 1:

The first step is to expand the recurrence equation by alternately applying the recurrence and simplifying the result until a pattern appears.

T_n = 2T_n-1 + 1

    = 2(2T_n-2 + 1) +1

     = 4 T_n-2 +2+1

    = 4(2T_n-3 + 1) +2+1

     = 8 T_n-3 + 4+2+1

     = 8(2T_n-4 + 1) +4+2+1

     =16 T_n-4 + 8+4+2+1

After several similar rounds of applying and simplifying, a pattern is apparent. The following formula seems to hold:

T_n = 2^k T_n-k + 2^k-1   +2^k-2 +….+ 2² +2¹+2⁰

       ⁼ 2^k T_n-k   +2^k -1

Step 2:

The next step is to verify the general formula with one more round of Applying and Simplifying :

T_n = 2^k   T_n-1 + 2^k – 1

    = 2^k (2T_n-(k+1) + 1) +2^k – 1

   = 2^k+1 T_n-(k+1) + 1 +2^k+1 – 1

The final expression on the right is the same as the expression on the first line, except that k is replaced by k + 1. Surprisingly, this effectively proves that the formula is correct for all k. Reason : we know the formula holds for k = 1, because that’s the original recurrence equation. And we’ve just shown that if the formula holds for some k >= 1, then it also holds for k + 1. So the formula holds for all k >= 1 by induction.

Step 3:

The last step is to express T_n as a function of early terms whose values are known. Here, choosing k = n - 1 expresses T_n in terms of T₁, which is equal to 1. Simplifying gives a closed-form expression for T_n:

T_n = 2^n-1 T₁ +2^n-1 -1

    = 2^n-1 . 1 +2^n-1 -1

    = 2ⁿ -1