Induction Proof of: Find $f(n)$ when $n=2^k$, where $f$ satisfies the recurrence relation $f(n)=f(\frac{n}2)+1$ with $f(1)=1$

Question

How can I proof this using regular induction and strong induction?

$$f(2^k)=f(\frac{2^k}2)+1=f(2^{k-1})+1$$ $$f(2^{1-1})=f(2^0)=f(1)=1$$ $$f(2^{2-1})=f(2^1)=f(2)=f(1)+1=2$$ $$f(2^{3-1})=f(2^2)=f(4)=f(2)+1=3$$ $$f(2^{4-1})=f(2^3)=f(8)=f(4)+1=4$$ $$f(2^{5-1})=f(2^4)=f(16)=f(8)+1=5$$

$$f(2^{k})=k$$

Answer 1

First, let $g(k) = f(2^k)$

$\therefore g(k)=g(k-1)+1 \implies g(k) = g(0) + k \implies f(2^k)= f(1)+k$

Now $f(1)=1 \implies f(2^k)=1+k$

Hence: $f(n) = 1 + \log_2 n$

Verify by induction:

Basis: $f(n)=1+\log_2 n \implies f(1) = 1$

Inductive step: $f(n)=1+\log_2 n \implies f(\frac n 2) = \log_2 n \implies f(n)=f(\frac n 2)+1$