This is part of a homework assignment I'm having trouble with and would be thankful for a little hint.
Let $a>b>1,c>0 \in \mathbb{N}$ and $T: \mathbb{N} \to \mathbb{N}$ defined recursively by $T(1) \leq c, T(n) \leq aT(\frac{n}{b})+cn$ and it can be assumed that $n=b^k$.
Show $T(n) \leq c \frac{a}{a-b} n^{log_b(a)}$ by induction.
My solution attempt:
Induction start:
$T(b^0) = T(1) \leq c \leq c \frac{a}{a-b} 1^{log_b(a)}$ is true since for $a>b>1$ we have $\frac{a}{a-b} = 1 + \frac{b}{a-b} \geq 1$.
Induction assumption:
$T(b^k) \leq c \frac{a}{a-b} (b^k)^{log_b(a)} = c \frac{a}{a-b} a^k$
Induction step from $T(b^k)$ to $T(b^{k+1})$:
$T(b^{k+1}) \leq a T(b^k) + cb^{k+1} \leq a [c \frac{a}{a-b} a^k ] + cb^{k+1} = c \frac{a}{a-b} a^{k+1} + cb^{k+1}$
But that is $ \not \leq c \frac{a}{a-b} a^{k+1}$, which is the right side I'm aiming for. Where did I go wrong?