Question

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{)}$

Short answer

The expression $f\left(n\right)=C_1{n}^d+C_2{n}^{{\log }_{b^a}}$is proved.

Step-by-step solution

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 $\mathit{n}$

Proceed via induction on k

Since $n$is a power of $b$so, $n=b^k$and $k={\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}^{{\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}$:

$$\begin{gathered} f\left(n\right)=af(n/b)+c{n}^d \\ 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^{{\log }_{b^a}} \\ f\left(n\right)=C_1{n}^d+C_2{n}^{{\log }_{b^a}} \end{gathered}$$

And the induction is complete.