# Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$.

This is seen here, for those who are interested:

What I want to know is how to show that if $a > b^d$, then $f(n)$ is $O(n^{log_ba})$?

Thank you!

-
How do you get $f(n)=af(n/b)+cn^d$ in the beginning of your inductive step ? – Dolma Apr 24 '13 at 20:07
Do you think that is wrong? – tekman22 Apr 24 '13 at 21:15
I didn't say it's wrong, just that I don't understand where it comes from. The only thing you know about the function $f$ is from the lemma you're trying to prove. In other words, at that time of the proof the only thing you can use about $f$ is its value for $n=b^k$, you can't say anything about its value for $n=b^{k+1}$. However, you might have some other information about $f$ that I don't know about, but for now I really don't see how you could possibly get this relation having no other information than what's in your post. – Dolma Apr 24 '13 at 21:26
Wow, well if it changes things, that shouldn't be $a! = b^d$ it should be $a$ $!=$ $b^d$.. – tekman22 Apr 24 '13 at 21:53
@Dolma Here is the image showing the proof in its entirety. Please let me know if there is something that appears wrong from this: gyazo.com/4dc761cba2cdeea403a30ef77cfa225b.png?1366840613 – tekman22 Apr 24 '13 at 21:57

## 1 Answer

If $a > b^{d}$ then $\log_{b}a > \log_{b}b^{d} = d$.

Hence $n^{d} < n^{\log_{b}a}$

and so

$C_{1}n^{d} + C_{2}n^{\log_{b}a} < (C_{1} + C_{2})n^{\log_{b}a}$,

so $f(n)$ is $O(n^{\log_{b}a})$.

-