Question

Suppose that $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathit{f}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{2}\mathbf{)}\mathbf{+}\mathbf{3}$when $\mathit{n}$ is an even positive integer, and $\mathit{f}\mathbf{\left(}\mathbf{1}\mathbf{\right)}\mathbf{=}\mathbf{5}$. Find

a)$\mathit{f}\mathbf{\left(}\mathbf{2}\mathbf{\right)}$

b)$\mathit{f}\mathbf{\left(}\mathbf{8}\mathbf{\right)}$.

c)$\mathit{f}\mathbf{\left(}\mathbf{64}\mathbf{\right)}$.

d)$\mathit{f}\left(1024\right)$.

Short answer

The answers are given below:

(a)$f\left(2\right)=13$

(b)$f\left(8\right)=61$

(c)$f\left(64\right)=509$

(d)$f\left(1024\right)=8189$

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:\(f(n) = 2f(n/2) + 3\,{\rm{and}}\,f(1) = 5\)

(a) Repeatedly apply the recurrence relation until we obtain\(n = 3\):

\(\begin{aligned}f(2) &= 2f(1) + 3\\ &= 2(5) + 3\\ &= 13\end{aligned}\)

(b) Repeatedly apply the recurrence relation until we obtain\(n = 8\):

\(\begin{aligned} f(4) &= 2f(2) + 3\\ &= 2(13) + 3\\ &= 29\\f(8) &= 2f(4) + 3\\ &= 2(29) + 3\\& = 61\end{aligned}\)

(c) Repeatedly apply the recurrence relation until we obtain\(n = 64\):

\(\begin{aligned}f(16) &= 2f(8) + 3\\f(16) &= 2(61) + 3\\ &= 125\\f(32) &= 2f(16) + 3\\ &= 2(125) + 3\\ &= 253\\f(64) &= 2f(32) + 3\\ &= 2(253) + 3\\ &= 509\end{aligned}\)

(d) Repeatedly apply the recurrence relation until we obtain\(n = 1024\):

\(\begin{aligned}f(128) &= 2f(64) + 3\\ &= 2(509) + 3\\ &= 1021\\f(256) &= 2f(128) + 3\\& = 2(1021) + 3\\ &= 2045\\f(512) &= 2f(256) + 3\\ &= 2(2045) + 3\\ &= 4093\\f(1024) &= 2f(512) + 3\\ &= 2(4093) + 3\\ &= 8189\end{aligned}\)