Q1. How to find a function $f(x)$ satisfying the recurrence relation $$f(2x) = f(x) + 1$$
Q2. Also how to prove that the closed form for the recurrence relation $$f(n) = f \left( \left \lfloor \frac n 2 \right \rfloor \right ) + 1$$ with $f(0) = 0$ is given by $f(n) = \lfloor \log_2 (n)\rfloor + 1$.
Asked
Active
Viewed 147 times
1
Mula Ko Saag
- 2,177
- 1
- 23
- 45
-
what is equal $f(1)$? or $f(0)$? – dato datuashvili Dec 13 '13 at 18:41
-
So $f(x)$ is not defined at $x=0$, correct? – abiessu Dec 13 '13 at 18:42
-
@datodatuashvili assume $f(1) = 0$ – Mula Ko Saag Dec 13 '13 at 18:42
-
"How do I show that a function ..." I guess you're asking "How do I find a function ..."? – John Dec 13 '13 at 18:45
-
@John sorry ...yes to that. After I put that function in W|A, i get the result but I don't know how to find it. – Mula Ko Saag Dec 13 '13 at 18:47
2 Answers
5
Q1 Since the recurrence relation only tells you what $f$ is at even integers, you are free to define it at the odd integers. Then, you can prove that
$$f(2^k(2m+1))=f(2m+1)+k \,,$$
where $f$ is defined any way you want on the odd integers.
A simple choice is to define $f(2m+1)=0$ for all $m$, and then the above formula yields $f(n)=$the power of $2$ in $n$.
Q2 Let $k:= \lfloor \log_2 (n)\rfloor $. Then $2^k \leq n < 2^{k+1}$.
Since
$$2^{k-1} \leq \lfloor \frac{n}{2} \rfloor < 2^k$$
Your result becomes an easy induction by $k$.
N. S.
- 132,525
0
For the first question, would $y=log_2x$ work? After all, $log_2(2x)=log_2x+1$ is a true statement? Just guessing here...
imranfat
- 10,029
-
-
-
This only attempts to answer half of the post, and it doesn't even answer the first half very confidently... would make a better comment. – rschwieb Dec 13 '13 at 19:26
-
@rschwieb I know, I was just trying. It works, but I have no proof of other functions that work other than changing the base of the logarithm. It was pure trial... – imranfat Dec 13 '13 at 19:31