can you please explain the induction step for me?

Lecture-1: The Fibonacci Sequence (cont.) . Theorem 1.1 If T(n) is the number of terms in the recursion tree corresponding to Algorithm 1.6, then, for n22, T(n) 2/2. Proof: The proof is by induction on n. Induction base: We need two base cases because the induction step assumes the results of two previous cases. For n = 2 and n = 3, the recursion in the recursion tree shows that T(2) = 3 > 2 = 22/2 T(3) = 5 > 2.832323/2 Induction hypothesis: Assume that the statement is true for all m 2m/2 Induction step: We must show that T(n) > 21/2. The value of T(n) is the sum of T(n 1) and T(n 2) plus the one node at the root. Therefore, ? T(n) =T(m - 1)+Tn - 2)+1 > 2(n-1)/2 + 2(n-3)/2 + 1 by induction hypothesis > 2(12)/2 + 2(n2)/2 = 2 x 2(?)-1 = 21/2