Page 1 of 1
Let S(n) be defined by the following recurrence relation. S(n)= ={$cn '-1 1 if n=1 S(n-1) + 2n-1 if n > 1 Let s(n) = n2.
Posted: Tue Nov 16, 2021 7:06 am
by answerhappygod
- Let S N Be Defined By The Following Recurrence Relation S N Cn 1 1 If N 1 S N 1 2n 1 If N 1 Let S N N2 1 (103.42 KiB) Viewed 44 times
Let S(n) be defined by the following recurrence relation. S(n)= ={$cn '-1 1 if n=1 S(n-1) + 2n-1 if n > 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. =k So, by induction, for all n 1.