Week 5

In the lecture on Oct 6th, we worked out a closed form for the function:
0, if n = 0
H(n) = { 2, if n = 1
3*H(n - 1) - 2*H(n - 2), if n > 1
which is H(n) = 2^(n + 1) - 2. Here is a proof of this formula by complete induction.

P(n): the closed form for the given function above is H(n) = 2^(n + 1) - 2.
Claim: \forall n \in N, P(n).
Proof: assume n \in N and P(0) /\ P(1) /\.../\P(n - 1) are true. Then either n <= 1 or n > 1.
Case 1: n <= 1. For n = 0, H(0) = 2^(0 + 1) - 2 = 2 - 2 = 0 which satisfies the defination of H(n) when n = 0. For n = 1, H(1) = 2^(1 + 1) - 2 = 4 - 2 = 2 which also satisfies the defination for n = 1. So H(0) and H(1) are true.
Case 2: n >= 1. According to the defination of H(n), H(n) = 3*H(n - 1) - 2*H(n - 2) = 3*(2^(n - 1 + 1) - 2) - 2*(2^(n - 2 + 1) - 2) = 3*2^n - 6 - 2*2^(n - 1) + 4 = 3*2^n - 2^n - 2 = 2*2^n - 2 = 2^(n + 1) - 2 which is the closed form for H(n).
So \forall n \in N, P(0) /\ P(1) /\.../\ P(n - 1) => P(n)
Thus, \forall n \in N, P(n).