Question

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

Short answer

Thus, $n=2^k$is equivalent with $k={\log }_{2}n$.

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply Recurrence Relation

Given information are $n=2^k,f\left(n\right)=f(n/2)+1 \text{and} f\left(1\right)=1$

Repeatedly apply the recurrence relation:

$$\begin{gathered} f\left(n\right)=f\left(2^k\right) \\ f\left(n\right)=f\left(2^{k-1}\right)+1 \\ f\left(n\right)=f\left(2^{k-2}\right)+2 \\ f\left(n\right)=\dots \\ f\left(n\right)=f\left(2^2\right)+(k-2) \\ f\left(n\right)=f\left(2^1\right)+(k-1) \\ f\left(n\right)=f\left(2^0\right)+k \\ f\left(n\right)=f\left(1\right)+k \\ f\left(n\right)=1+k \\ f\left(n\right)=k+1 \\ f\left(n\right)={\log }_{2}n+1 \end{gathered}$$

Therefore, $n=2^k$is equivalent with $k={\log }_{2}n$.