B. Closed-Form Solutions and Induction Let S(n) be defined by the following recurrence relation. 1 if n = 1 s(n) =\\ S(n-1) + 2n-1 ifn> 1 Let s(n) = n2. Fill in the blanks in the following proof that S(n) = s(n) for all n 2 1. We use induction on n. Base Case: If n = 1, the recurrence relation says that S(1) = , and the closed-form formula says that s(1) = ,so S(1) = s(1). Inductive Hypothesis: Let k > 1. Suppose as inductive hypothesis that S(k - 1) = Inductive Step: Using the recurrence relation, S(k) = by the recurrence relation by inductive hypothesis using algebra. = 12 So, by induction, for all n 2 1