GATE CSE 2022 | Question: 41

Question

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

• A. $f(2^{n} – 1) = 2^{n} – 1$
• B. $f(2^{n}) = 1$
• C. $f(5 \cdot 2^{n}) = 2^{n+1} + 1$
• D. $f(2^{n} + 1) = 2^{n} + 1$

Comments

Check with f(33)  for this option D is wrong.

---

f(5) = 3 ; we can make wrong Option D with ths example .

---

@SilentClimber Thanks this method is useful to get the answer quickly for this question 👍

Answer 1

$\textbf{Edit:}$ To do this question quickly in exam, you can do something like informal induction:

$A)$ Let, $f(2^n - 1) = 2^n - 1$ is true for all natural $n \geq 1$, it means $f(2^{n-1} - 1) = 2^{n-1} - 1$ is also true for $n \geq 2$.

Now,

$f(2^n-1) = f((2^n - 1 -1)+1) = f(2^n -2 + 1) = f(2(2^{n-1}-1)+1)$

$ = 2f(2^{n-1}-1)+1 = 2(2^{n-1}-1)+1 = 2^n - 1$

Similarly,

$B)$ $f(2^n) = f(2\times2^{n-1}) = 2f(2^{n-1}) - 1 = 2\times 1 -1 = 1$

$C)$ $f(5.2^n) = f(2(5\times2^{n-1})) = 2f(5\times 2^{n-1})-1$

$ = 2 \times (2^n + 1) - 1 = 2^{n+1} + 1$

$D)$ $f(2^n + 1) = f(2\times 2^{n-1} + 1) = 2f(2^{n-1}) + 1 = 2 \times 1 + 1 = 3$

Hence, A,B and C are correct options.
 

-----------------------------------------------------------------------------------------------------------------------

Given: $f(2n) = 2f(n)-1$ and $f(2n+1)=2f(n) + 1$ for $n \geq 1$

Now, I shall check options one by one.

$\textbf{Option (B)}:$

$f(2^n) = 2f(\frac{2^n}{2}) -1 $ $[\because 2^n$ is an even term for $n\geq 1$ and since for even terms recurrence is defined as $f(2n) = 2f(n)-1$  which can be written as $f(n) = 2f(\frac{n}{2})-1$ So, I can write $f(2^n)$ as $2f(\frac{2^n}{2}) -1 $]

So, $f(2^n) = 2f(2^{n-1}) -1$

$=2[2f(2^{n-2})-1]-1= 2^2f(2^{n-2})-2-1$

Like this I can write:

$f(2^n) = 2^kf(2^{n-k})-2^{k-1}-2^{k-2}-...-1$

Put $n-k=0 \implies k=n$

So, $f(2^n) = 2^n*1 -(1+2+...+2^{n-1}) = 2^n – \left(\frac{1*(2^n-1)}{2-1} \right) = 2^n – 2^n +1 = 1$

Hence, $f(2^n) = 1$

$\textbf{Option (A)}:$

Since, $2^n-1$ is an odd term for $n \geq 1$ So, I can get the value of $f(2^n-1)$ from the recurrence which is defined for odd terms i.e. $f(2n+1)=2f(n) + 1$ which can be written as $f(n)= f(\frac{n-1}{2}) + 1$

So, $f(2^n -1) = 2f(\frac{2^n-1-1}{2}) = 2f(\frac{2^n-2}{2}) + 1 = 2f(2^{n-1}-1) +1 $

So,  $f(2^n -1) = 2f(2^{n-1}-1) +1 $

$= 2[2f(2^{n-2} – 1)+1]+1 = 2^2f(2^{n-2}-1)+2 + 1$

Like this I can write as:

$f(2^n – 1) = 2^kf(2^{n-k}-1) + 2^{k-1} +2^{k-2}+...+1$

Put $2^{n-k}-1 = 1 \implies 2^{n-k} = 2 \implies n-k=1 \implies  k=n-1$

So,

$f(2^n – 1) = 2^{n-1}*1 + 2^{n-2} + 2^{n-3}+...+1 = 1+2+….+2^{n-1}$

$= \left(\frac{2^n-1}{2-1}\right) = 2^n – 1$

So, $f(2^n – 1) = 2^n – 1$

$\textbf{Option (C)}:$

For $n \geq 1,$ $5 \times 2^n$ will give an even value, So, I can use recurrence which is defined for even terms i.e. $f(2n) = 2f(n)-1$  which can be written as $f(n) = 2f(\frac{n}{2})-1$ So, I can write $f(5 \times 2^n)$ as $2f(\frac{5\times2^n}{2}) -1 $]

So,

$f(5 \times 2^n) = 2f(5 \times 2^{n-1}) – 1$

$= 2 [ 2f(5 \times 2^{n-2}) – 1] -1 = 2^2 f(5 \times 2^{n-2}) – 2 -1$

Like this I can write:

$f(5 \times 2^n) = 2^kf(5\times 2^{n-k}) – 2^{k-1} – 2^{k-2}-...-2^0$

Since $f(5 \times 2^1) = f(10) = 2f(5)-1 = 2[2f(2)+1]-1 = 2[2+1]-1 =5$

So, put $5\times 2^{n-k} = 10 \implies 2^{n-k} = 2^1 \implies n-k = 1 \implies k=n-1$

So,

$f(5 \times 2^n) = 2^{n-1} \times 5 – 2^{n-2} – 2^{n-3} -...-1 = 5\times 2^{n-1} – [1+2+...+2^{n-2}]$

$f(5 \times 2^n) = 5 \times 2^{n-1} – \left(\frac{2^{n-1}-1}{2-1}\right) =  5 \times 2^{n-1} – 2^{n-1} + 1 = 2^{n-1}(5-1) + 1 $

$f(5 \times 2^n)= 2^{n-1}\times 2^2 + 1 = 2^{n+1} + 1$

$\textbf{Option (D)}:$

Since, $2^n + 1$ is an odd value for $n \geq 1$, So, I can get the values for $f(2^n + 1)$ from the recurrence which is defined for odd values of $f.$ i.e. $f(2n+1)=2f(n) + 1$ which can be written as $f(n)= f(\frac{n-1}{2}) + 1$

So,

$f(2^n +1 ) = 2f (\frac{2^n +1 -1}{2})+1 = 2 f(2^{n-1})+1 = 2\times1 +1 = 3$

Hence, $\textbf{Answer: A,B,C}$ (By putting values of $n$ and evaluating $f(.)$, we can eliminate some option also here.)

Comments

i understood the approach but in exam it's better to find values of small values and choose the answer and if we got extra time then we can subtitude and try to find the actual formula to recheck our answer?

---

@S_Sandeep we are here to learn things. A 10th or 12th class student can eliminate options for MCQs by substituting values if just instructed him but what did you learn for that question. Also, most of the times in subjective exams or if you study in good college then it would not work. In exam, at the end, you have to do that things like substituting values to save time but in my opinion you should also know how to solve questions if options are not given and you should try to invent new methods and techniques as well if you have time.   

Goal should be to learn things with different methods/techniques so that it can improve the thinking capability and would helpful for rest of the life.

---

@ankitgupta.1729 Roger that sir.

Answer 2

$\underline{\textbf{Answer: A, B, C}}$
$\underline{\textbf{Explanation:}}$ This question is a very interesting and standard question. The best way to observe this is by looking at the table which I have made. Once, you observe the table you can do it orally and also create your own set of recurrence solutions for the given recurrence in terms of function \mathbf n.

For proof-like solutions, you can refer “Ankit Gupta’s” approach to this problem.

Though I have made an entire table for $31$ set of values to get the feel of the pattern. But still, let's calculate a few ones by following the recurrence given in the question (exam procedure).
$\mathrm{f(1) = \enclose{circle}{1}, [Given]}$
$\mathrm{f(2) = f(2\times \color {red}1) = 2f(\color{red}1)-1 = 2 \times 1 – 1 = \enclose{circle}{1}}$
$\mathrm{f(3) = f(2\times \color{red}1+1) = 2\times f(\color{red}1)+1 = 2\times1+1 = \enclose{circle}{3}}$
$\mathrm{f(4) = f(2\times \color {red} 2) = 2\times f(\color {red} 2)-1 = 2 \times1-1 = \enclose{circle}{1}}$
$\mathrm{f(5) = f(2\times \color {red} 2+1) = 2\times f(\color {red} 2)+1 =2\times1+1 = \enclose{circle}{\color {green}{\underline 3}} }$
$\mathrm{f(6) = \enclose{circle}{5}}$
$\mathrm{f(7) = f(2\times \color {red}3+1) = 2f(\color{red}3)+1 = 2\times3+1 = \enclose{circle}{7}}$
$\mathrm{f(8) = \enclose{circle}{1}}$
$\mathrm{f(9) = f(2\times \color {red} 4 + 1) = 2\times f(4) + 1 = 2\times 1 +1 = \enclose{circle}{\color {green} {\underline{3}}}}$
$\mathrm{f(10) = \enclose{circle}{5}}$
$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots $
Now, we can eliminate the options by simply substituting the values. $\text{[A much much easier method to solve recursive questions in GATE]}$
$\underline{\mathbf{Option\;B:}}$
Anything raised to power $\mathbf 2$ always produces $\mathbf{Even}$ values. Hence,  for $\textbf{Option B}$, we should always get $\mathbf 1$ as the answer, which is $\mathbf{TRUE}$. We can also verify from the table that for every column the first value is always $\mathbf 1$.

$\underline{\mathbf{Option\;C}}$
$\mathrm{f(5.2^n)=2^n+1}$, Substitute few values of $\mathbf n$. For example, we will get something like: $f(5), f(10), f(20), f(40),...$. Calculate few values or you can verify from the table as well.

$\underline{\textbf{Option D:}}$
$\mathrm{f(2^n+1)}$ will always produce terms like, $\textbf{2+1, 4+1, 8+1, 16+1, ...}$, but from the below table it is clearly visible that for such values, the answer is always a constant $3$. $\therefore$ Correct recurrence would be: $\color{orange}{f(2^n + 1) = 3}$. Also, this value is always the $2^{nd}$ term in each column.

$\color{red}{\textbf{Alternate approach without table for this option.}}$ Check for few values like $\textbf{n = 1, 2, 3,..}$ and observe.

$\underline{\textbf{Option A:}}$
$\mathrm{f(2^4-1) =f(15) = 2^4-1 = 15 = \mathbf n}$. So, this produces $\mathbf n$ for given $\mathbf n$. Hence, $\textbf{TRUE.}$

We can also verify from the table, that this function produces the last value in every table which is same for the given $\mathbf n$ on both LHS and RHS side.

$\underline{\underline{\color{red}{{f(1) = 1}}}}$ $\color{dark violet}{\underbrace{\mathbf{2^0 = 1}\;\text{elements}}}$

$\color{red}{f(2) = 1}$ $\color{orange}{f(3) = 3}$  $\color{dark violet}{\underbrace{\mathbf{2^1 = 2}\;\text{elements}}}$

$\color{red}{f(4)=1}$ $f(5) =3 $ $\color{green}{f(6) = 5}$ $\color{orange}{f(7) = 7}$ $\color{dark violet}{\underbrace{\mathbf{2^2 = 4}\;\text{elements}}}$

$\color{red}{f(8) = 1}$ $f(9) = 3$ $\color{blue}{f(10)=5}$ $f(11) = 7$ $f(12) = 9$ $f(13) = 11$ $\color{green}{f(14) = 13}$ $\color{orange}{f(15) = 15}$ $\color{dark violet}{\underbrace{\mathbf{2^3 = 8}\;\text{elements}}}$

$\color{red}{f(16) = 1}$ $f(17) = 3$ $f(18) = 5$ $f(19) = 7$ $\color{blue}{f(20) = 9}$ $f(21) = 11$ $f(22) = 13$ $f(23) = 15$ $f(24) = 17$ $f(25) = 19$ $f(26) = 21$ $f(27) = 23$ $f(28) = 25$ $f(29) = 27$ $\color{green}{f(30) = 29}$ $\color{orange}{f(31) = 31}$ $\color{dark violet}{\underbrace{\mathbf{2^4 = 16}\;\text{elements}}}$

 

 

 

 

Comments

I think answer should be A,B,C

---

@`JEET answer will be A,B,C

---

Right.

Thanks

Answer 3

Woah! I always wanted them to ask this, famous “THE JOSEPHUS PROBLEM,“ which all of us might have heard in one or the other form.

Refer to section 1.3 here to get all inside out of this recursion.

BTW A,B,C are correct

$F(2^m + l) =  2*l + 1 \quad ; \quad 0 \leq l < 2^m $  

(Please, refer the given link for complete explanation of how we reach to this equation.)

Now, Option (A): Correct

$f(2^n – 1) = f(2^{n-1} + 2^{n-1}-1) = 2*(2^{n-1} -1) + 1 = 2^n -2 + 1 = 2^n -1$

 

Option (B): Correct

$f(2^n) = f(2^n + 0) = 2*0 + 1 =1 $

 

Option C: Correct

$f(5 \cdot 2^n) = f(4\cdot 2^n + 2^n) = f(2^{n+2} + 2^n) = 2 \cdot 2^n + 1 = 2^{n+1} +1$

 

Option D: Wrong

$f(2^n + 1) = 2*1 + 1 = 3$

Comments

@Nikhil_dhama

Bro,the link is dead. Can you give another reference?

Ok, I found this reference to be helpful : https://sam.nitk.ac.in/courses/MA201/Josephus_problem.pdf

---

@P0535_Yedidyah_Sagar link was for the knuth's concrete mathematics book.

https://seriouscomputerist.atariverse.com/media/pdf/book/Concrete%20Mathematics.pdf

you can find the problem in first chapter. Also this is a very good book and highly recommended.

---

Thank you very much Ankit Bhai

Answer 4

Induction can also be used to prove these identities. We guess the solution and then prove it by induction but guessing is the hard part of the induction. But if the options are given then it means, we know the expression and we just have to prove it or disprove it.

One more way to guess the solution of recurrence is to observe the pattern after finding $f(.)$ for initial few values of $n$. So, here, finding the pattern is easy and we can guess the solution easily and then we only need to prove it by induction.

Since, options are given, I will use induction on $n$ and I will use shorthand notations $\textbf{IH}$ for Inductive Hypothesis and $\textbf{IS}$ for Inductive Step.

Since, $f(2n) = 2f(n) – 1$, for integer $n \geq 1$

Let, $2n = m \implies n = \frac{m}{2}$ So, $f(m) = 2f\left(\frac{m}{2}\right) - 1 \implies f(n) = 2f\left(\frac{n}{2}\right) - 1$ and

  $f(2n+ 1) = 2f(n) + 1$, for integer $n \geq 1$

Let, $2n+1 = m \implies n = \frac{m-1}{2}$ So, $f(m) = 2f\left(\frac{m-1}{2}\right) + 1 \implies f(n) = 2f\left(\frac{n-1}{2}\right) + 1$

So, if $f(2n) = f(even),$ I will use $ f(n) = 2f\left(\frac{n}{2}\right) - 1$ and if $f(2n+1) = f(odd),$ I will use $ f(n) = 2f\left(\frac{n-1}{2}\right) + 1$. Now,

$A)$ $f(2^n – 1) \stackrel{?}{=} 2^n -1$

$\textbf{Basis:}$ For $n=1,$ $f(2^1-1) = 2^1 – 1 = 1 $ and it is given that $f(1) = 1.$ So, True.

$\textbf{IH:}$ Suppose $f(2^n – 1) = 2^n – 1$ is True (or) $f(2^m – 1) = 2^m – 1$ is True for all integer $ m \leq n$

$\textbf{IS:}$ We need to check $f(2^{n+1} – 1) \stackrel{?}{=} 2^{n+1} -1$ means whether $f(2^{n+1}-1) = 2^{n+1} -1$ is True or not.

$f(\underbrace{2^{n+1} - 1}_{odd}) = 2f\left(\frac{2^{n+1} - 1 -1}{2} \right) + 1 = 2f\left(\frac{2^{n+1} - 2}{2} \right) + 1 = 2f\left(2^n – 1 \right) + 1 = 2(2^n – 1) + 1 = 2^{n+1} – 1.$ Q.E.D.

 

$B)$ $f(2^n) \stackrel{?}{=} 1$

$\textbf{Basis:}$ For $n=0,$ $f(2^0)  = 1 $ and it is given that $f(1) = 1.$ So, True.

$\textbf{IH:}$ Suppose $f(2^n ) = 1$ is True (or) $f(2^m ) = 1$ is True for all integer $ m \leq n$

$\textbf{IS:}$ We need to check $f(2^{n+1}) \stackrel{?}{=} 1$ means whether $f(2^{n+1}) = 1$ is True or not.

$f(\underbrace{2^{n+1}}_{even}) = 2f\left(\frac{2^{n+1}}{2} \right) - 1 = 2f\left(2^n \right) - 1 = 2 \times 1 - 1 = 1.$ Q.E.D.

 

$C)$ $f(5.2^n) \stackrel{?}{=} 2^{n+1} + 1$

$\textbf{Basis:}$ For $n=0,$ $f(5)  = 2f\left(\frac{5-1}{2}\right) + 1 = 2f(2) + 1 = 2[2f(1)-1] + 1 =2[2\times 1 – 1] + 1 = 3 $ and it is given that $f(5) = 2^{0+1} + 1 = 3.$ So, True.

$\textbf{IH:}$ Suppose $f(5.2^n ) = 2^{n+1} + 1$ is True (or) $f(5.2^m ) = 2^{m+1}+ 1$ is True for all integer $ m \leq n$

$\textbf{IS:}$ We need to check $f(5.2^{n+1}) \stackrel{?}{=} 2^{n+2} + 1$ means whether $f(5.2^{n+1}) = 2^{n+2} + 1$ is True or not.

$f(\underbrace{5.2^{n+1}}_{even}) = 2f\left(\frac{5.2^{n+1}}{2} \right) - 1 = 2f\left(5.2^n \right) - 1 = 2 [2^{n+1} + 1] - 1 = 2^{n+2} + 1.$ Q.E.D.

$D)$ $f(2^n + 1) \stackrel{?}{=} 2^{n} + 1$

$\textbf{Basis:}$ For $n=0,$ $f(2)  = 2f\left(\frac{2}{2}\right) - 1 = 2f(1) - 1  = 1 $ but according to given expression, $f(2) = 2^{0} + 1 =2.$ So, False.

( I am writing this answer separately because previous answer will be long if I edit it by adding this answer. )

Answer 5

Put n = 3
A, B, C satisfies the given solution.
while for D option its wrong because f(2^3 + 1) = f(9) == 3 & f(9) != 9
Sometimes solving in dumb way is smart .

Answer 6

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