retagged by
7,589 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

21 votes
21 votes
$\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.)
edited by
11 votes
11 votes

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

 

 

 

 

edited by
5 votes
5 votes

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$

edited by
2 votes
2 votes
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:

Related questions