• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q8E

Expert-verified Found in: Page 535 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Suppose that ${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{2}}{\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{/}}{\mathbf{2}}{\mathbf{\right)}}{\mathbf{+}}{\mathbf{3}}$ when ${\mathbit{n}}$ is an even positive integer, and ${\mathbit{f}}{\mathbf{\left(}}{\mathbf{1}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{5}}$. Finda)${\mathbit{f}}{\mathbf{\left(}}{\mathbf{2}}{\mathbf{\right)}}$b)${\mathbit{f}}{\mathbf{\left(}}{\mathbf{8}}{\mathbf{\right)}}$.c)${\mathbit{f}}{\mathbf{\left(}}{\mathbf{64}}{\mathbf{\right)}}$.d)${\mathbit{f}}\left(1024\right)$.

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

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

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

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

See the step by step solution

## Step 1: 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}}}$

## Step 2: 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}

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades. 