Q41MSQ2 marksConsider the following recurrence: f(1)=1;f(2n)=2f(n)–1, for n≥1;f(2n+1)=2f(n)+1, for n≥1.\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) – 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text{for}\; n \geq 1. \end{array}f(1)f(2n)f(2n+1)===1;2f(n)–1,2f(n)+1,forn≥1;forn≥1. Then, which of the following statements is/are TRUE?\text{TRUE}?TRUE?(A)f(2n–1)=2n–1f(2^{n} – 1) = 2^{n} – 1f(2n–1)=2n–1(B)f(2n)=1f(2^{n}) = 1f(2n)=1(C)f(5⋅2n)=2n+1+1f(5 \cdot 2^{n}) = 2^{n+1} + 1f(5⋅2n)=2n+1+1(D)f(2n+1)=2n+1f(2^{n} + 1) = 2^{n} + 1f(2n+1)=2n+1Sign in to save attempts.Show answer← PreviousNext →SolutionsDiscussionLoading…Sign in with Google