• :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! Q31E

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

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that if ${\mathbit{a}}{\mathbf{\ne }}{{\mathbit{b}}}^{{\mathbf{d}}}$ and ${\mathbit{n}}$ is a power of ${\mathbit{b}}$, then ${\mathbit{f}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}{\mathbf{=}}{{\mathbit{C}}}_{{\mathbf{1}}}{{\mathbit{n}}}^{{\mathbf{d}}}{\mathbf{+}}{{\mathbit{C}}}_{{\mathbf{2}}}{{\mathbit{n}}}^{{\mathbf{log}}_{{\mathbf{b}}^{\mathbf{a}}}}$, where ${{\mathbit{C}}}_{\mathbf{1}\mathbf{=}}{{\mathbit{b}}}^{{\mathbf{d}}}{\mathbit{c}}{\mathbf{/}}{\mathbf{\left(}}{{\mathbit{b}}}^{{\mathbf{d}}}{\mathbf{-}}{\mathbit{a}}{\mathbf{\right)}}$ and ${{\mathbit{C}}}_{{\mathbf{2}}}{\mathbf{=}}{\mathbit{f}}{\mathbf{\left(}}{\mathbf{1}}{\mathbf{\right)}}{\mathbf{+}}{{\mathbit{b}}}^{{\mathbf{d}}}{\mathbf{/}}{\mathbf{\left(}}{\mathbit{a}}{\mathbf{-}}{{\mathbit{b}}}^{{\mathbf{d}}}{\mathbf{\right)}}$

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

See the step by step solution

## Step 1: Define the Induction formula

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

## Step 2: Proceed via induction on k

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/\left({b}^{d}-a\right)+f\left(1\right)+{b}^{d}c/\left(a-{b}^{d}\right)=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\left(n/b\right)+c{n}^{d}\phantom{\rule{0ex}{0ex}}f\left(n\right)=\left({b}^{d}c/\left({b}^{d}-a\right)\right){n}^{d}+\left(f\left(1\right)+{b}^{d}c/\left(a-{b}^{d}\right)\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. ### Want to see more solutions like these? 