StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q31E

Expert-verifiedFound in: Page 536

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Show that if ${\mathit{a}}{\mathbf{\ne}}{{\mathit{b}}}^{{\mathbf{d}}}$ and ${\mathit{n}}$ is a power of ${\mathit{b}}$, then ${\mathit{f}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}{\mathbf{=}}{{\mathit{C}}}_{{\mathbf{1}}}{{\mathit{n}}}^{{\mathbf{d}}}{\mathbf{+}}{{\mathit{C}}}_{{\mathbf{2}}}{{\mathit{n}}}^{{\mathbf{log}}_{{\mathbf{b}}^{\mathbf{a}}}}$, where ${{\mathit{C}}}_{\mathbf{1}\mathbf{=}}{{\mathit{b}}}^{{\mathbf{d}}}{\mathit{c}}{\mathbf{/}}{\mathbf{(}}{{\mathit{b}}}^{{\mathbf{d}}}{\mathbf{-}}{\mathit{a}}{\mathbf{)}}$ and ${{\mathit{C}}}_{{\mathbf{2}}}{\mathbf{=}}{\mathit{f}}{\mathbf{\left(}}{\mathbf{1}}{\mathbf{\right)}}{\mathbf{+}}{{\mathit{b}}}^{{\mathbf{d}}}{\mathbf{/}}{\mathbf{(}}{\mathit{a}}{\mathbf{-}}{{\mathit{b}}}^{{\mathbf{d}}}{\mathbf{)}}$**

The expression $f\left(n\right)={C}_{1}{n}^{d}+{C}_{2}{n}^{{\mathrm{log}}_{{b}^{a}}}$ is proved.

**Mathematical Induction is a technique of proving a statement, theorem, or formula which is thought to be true, for each and every natural number ${\mathit{n}}$**

Since $n$ is a power of $b$ so, $n={b}^{k}$ and $k={\mathrm{log}}_{b}n$ for some constant $k$.

For our base case, if $n=1$ and $k=0$ then: ${C}_{1}{n}^{d}+{C}_{2}{n}^{{\mathrm{log}}_{{b}^{a}}}={C}_{1}+{C}_{2}={b}^{d}c/({b}^{d}-a)+f\left(1\right)+{b}^{d}c/(a-{b}^{d})=f\left(1\right)$

Now, for inductive hypothesis assume true for $k$ with $n={b}^{k}$.

Next, for $n={b}^{k+1}$:

$f\left(n\right)=af(n/b)+c{n}^{d}\phantom{\rule{0ex}{0ex}}f\left(n\right)=({b}^{d}c/({b}^{d}-a\left)\right){n}^{d}+\left(f\right(1)+{b}^{d}c/(a-{b}^{d}\left)\right){n}^{{\mathrm{log}}_{{b}^{a}}}\phantom{\rule{0ex}{0ex}}f\left(n\right)={C}_{1}{n}^{d}+{C}_{2}{n}^{{\mathrm{log}}_{{b}^{a}}}$

And the induction is complete.

94% of StudySmarter users get better grades.

Sign up for free