in Combinatory retagged ago by
2,534 views
7 votes
7 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$
in Combinatory retagged ago by
by
2.5k views

1 comment

I think this is the question number $51$ in the original paper.
0
0

6 Answers

8 votes
8 votes
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 options also here.)

2 Comments

Bhai you should and must do a phd in maths.
4
4
I believe he did his masters from ISI , no doubt he is strong in mathematics 🧮
0
0
4 votes
4 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(\color{red}1) = 1, [Given]}$
$\mathrm{f(2) = f(2\times \color {red}1) = 2f(\color{red}1)-1 = 2 \times 1 – 1 = 1}$
$\mathrm{f(3) = f(2\times \color{red}1+1) = 2\times f(\color{red}1)+1 = 2\times1+1 = 3}$
$\mathrm{f(4) = f(2\times \color {red} 2) = 2\times f(\color {red} 2)-1 = 2 \times1-1 = 1}$
$\mathrm{f(5) = f(2\times \color {red} 2+1) = 2\times f(\color {red} 2)+1 =2\times1+1 = \color {green}{\underline 3} }$
$\mathrm{f(6) = 5}$
$\mathrm{f(7) = f(2\times \color {red}3+1) = 2f(\color{red}3)+1 = 2\times3+1 = 7}$
$\mathrm{f(8) = 1}$
$\mathrm{f(9) = f(2\times \color {red} 4 + 1) = 2\times f(4) + 1 = 2\times 1 +1 = \color {green} {\underline{3}}}$
$\mathrm{f(10) = 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
by

4 Comments

I think answer should be A,B,C
1
1

@`JEET answer will be A,B,C

1
1
Right.

Thanks
0
0
2 votes
2 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 Comments

In $(A),$ $2^n \neq 2^{\frac{n}{2}} + 2^{\frac{n}{2}}$

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

Personally, I have done M.Tech but still didn’t know about this problem and My friend who has completed only B.Tech knows about it. So, it might be possible that many people don’t know about this problem. And If they know about it then deriving the identity in exam is not easy. It can be solved If they have good memory to remember this identity.
2
2
Thanks for pointing out the mistake.

I thought it was a very famous puzzle; I have known about it since school. Maybe someone who likes solving puzzles a lot might have heard about it :p.
1
1
1 vote
1 vote
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