 Suggested languages for you:

Europe

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

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

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Find ${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}$ when ${\mathbit{n}}{\mathbf{=}}{{\mathbf{2}}}^{{\mathbf{k}}}$, where ${\mathbit{f}}$ satisfies the recurrence relation ${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}{\mathbf{=}}{\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{/}}{\mathbf{2}}{\mathbf{\right)}}{\mathbf{+}}{\mathbf{1}}$with ${\mathbit{f}}{\mathbf{\left(}}{\mathbf{1}}{\mathbf{\right)}}{\mathbf{=}}{\mathbf{1}}$.

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

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 information are $n={2}^{k},f\left(n\right)=f\left(n/2\right)+1 \text{and} f\left(1\right)=1$

Repeatedly apply the recurrence relation:

$f\left(n\right)=f\left({2}^{k}\right)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{k-1}\right)+1\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{k-2}\right)+2\phantom{\rule{0ex}{0ex}}f\left(n\right)=\dots \phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{2}\right)+\left(k-2\right)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{1}\right)+\left(k-1\right)\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left({2}^{0}\right)+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=f\left(1\right)+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=1+k\phantom{\rule{0ex}{0ex}}f\left(n\right)=k+1\phantom{\rule{0ex}{0ex}}f\left(n\right)={\mathrm{log}}_{2}n+1\phantom{\rule{0ex}{0ex}}$

Therefore, $n={2}^{k}$ is equivalent with $k={\mathrm{log}}_{2}n$. ### Want to see more solutions like these? 