Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Question

Given: $f(1) = 1$.

Answer:

$$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$

How do I find the value of $f(n)$ where $n$ is an odd integer?

Let say $f(3) = f\left(\frac{3}{2}\right) + 1$ which is it by the way. Then the question comes up what would the value of $f\left(\frac{3}{2}\right)$ be?

Answer 1

Unless you give some more initial terms, it is not possible to find $f(n)$ where $n$ is not a power of $2$.

When $n = 2^k,$ I claim that $f(2^k) = k+1$ for $k \ge 1$. This is true for $f(2)$ so assume it holds for some $k = j > 1$. Then $f(2^{j+1}) = f(2^j)+1 = j+2$ so we are done.

Answer 2

As already mentioned, without more initial conditions, you cannot compute terms using the recurrence. However, if you note that $$f(n) = \log_2 (n) +1$$ (Which should be proven by induction)

You can then extend the function to accept all real numbers.

Answer 3

#Steps

1.Subtitue n = 2^k

f(2^k) = f((2^k)/2) + 1

2.Find Pattern in Values of f(2^k)

• f(2^0) = f(1) = 1
• f(2^1) = f(2) = f(2/2) + 1 = f(1) + 1 = 1 + 1 = 2
• f(2^2) = f(4) = f(4/2) + 1 = f(2) + 1 = 2 + 1 = 3
• f(2^3) = f(8) = f(8/2) + 1 = f(4) + 1 = 3 + 1 = 4

k = 0,1,2,3... f(2^k) = 1,2,3,4

3.Create Formula

f(2^k) is always 1 greater than k

f(2^k) = k + 1

4.Create Formula using n

f(n) = k + 1

5.Rearrange to find k

n = 2^k

k = log2(n)

6.Create Formula using n, and remove k

f(n) = log2(n) + 1