retagged by
7,592 views
15 votes
15 votes

Consider the following recurrence:

$$\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}$$

Then, which of the following statements is/are $\text{TRUE}?$

  1. $f(2^{n} – 1) = 2^{n} – 1$
  2. $f(2^{n}) = 1$
  3. $f(5 \cdot 2^{n}) = 2^{n+1} + 1$
  4. $f(2^{n} + 1) = 2^{n} + 1$
retagged by

6 Answers

0 votes
0 votes

given in question  f (1)=1

f(2n)=2f(n)-1{equation one}

f(2n+1)=2f(n)+1 {equation second }

lets start with finding 

putting n=1 in equation 1

f(2)=2f(1)-1=1

f(3)=3  using equation second by putting n=1

using equation alternate

f(4)=1

f(5)=3
f(6)=5

f(7)=7

f(8)=1

f(9)=3

f(10)=5

going option number A 

put n=2

f(3)=3 valid so A is correct

going option B put n=2

f(4)=1 valid option B also correct

going option c put n=1

f(10)=  5    valid  so option c is correct

going option D put n=2

f(5)=5 invalid so  D is false 

so overall option A ,B,C is correct 

 

 

0 votes
0 votes
You don’t need so much analysis or induction here. For fast solving observe the terminating condition of the recurrence which is F(1)=1.

Now just put n=1 in every option and verify the result. For n=1 all the option will be correct.

Choose little higher value of n like 8 or 9 and put them in the options you’ll see option D will give you incorrect result.
Answer:

Related questions