Proof of closed-form expression for a recursive formula by induction With $f:\mathbb{N}\rightarrow\mathbb{R}_+$ and
$$T(1)=b$$
$$T(n)=a*T\left(\frac{n}{c}\right)+f(n)$$
for
$$a,b,c>0$$
$$n>1$$
Prove by induction that
$$T(n)=\sum_{i=0}^k \left(a^i * f\left(\frac{n}{c^î}\right)\right)$$
is valid when $f(1)=b$ for all $n=c^k$ with $k\in\mathbb{N}$.
My solution: It's easy to see that the formula is valid for $k=0$ ($n=1$). But I am stuck at the induction step:
$$T(c^{k+1})=a*T(c^k)+f(c^{k+1})$$
$$T(c^{k+1})=a*\sum_{i=0}^k \left(a^i * f\left(\frac{c^k}{c^î}\right)\right)+f(c^{k+1})$$
$$T(c^{k+1})=a*\sum_{i=0}^{k+1} \left(a^i * f\left(\frac{c^k}{c^î}\right)\right)-a^{k+2}*f\left(\frac{c^k}{c^{k+1}}\right)+f(c^{k+1})$$
$$T(c^{k+1})=\sum_{i=0}^{k+1} \left(a^{i+1} * f\left(\frac{c^{k+1}}{c^{î+1}}\right)\right)-a^{k+2}*f\left(\frac{1}{c}\right)+f(c^{k+1})$$
And now I am stuck. At the end the formula should look like this:
$$T(c^{k+1})=\sum_{i=0}^{k+1} \left(a^i * f\left(\frac{c^{k+1}}{c^î}\right)\right)$$
But I don't see the steps in between.
 A: You've got the right idea, but you made a mistake trying to initially add one more term to the summation and then subtract it, as this leads to dealing with $f\left(\frac{1}{c}\right)$ which is not defined. Here is how you can proceed instead starting from the second line of your induction step, with the steps below being similar to what you also did later:
$$\begin{equation}\begin{aligned}
T(c^{k+1}) & = a \times\sum_{i=0}^k \left(a^i \times f\left(\frac{c^k}{c^i}\right)\right) + f(c^{k+1}) \\
& = \sum_{i=0}^k \left(a^{i+1} \times f\left(\frac{c^{k+1}}{c^{i+1}}\right)\right) + a^{0} \times f\left(\frac{c^{k+1}}{c^0}\right) \\
& = \sum_{i=1}^{k+1} \left(a^{i} \times f\left(\frac{c^{k+1}}{c^{i}}\right)\right) + a^{0} \times f\left(\frac{c^{k+1}}{c^0}\right) \\
& = \sum_{i=0}^{k+1} \left(a^{i} \times f\left(\frac{c^{k+1}}{c^{i}}\right)\right)
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
Note that going from the second to the third lines above with the summation, I increased the summation limits of $i$ by $1$, so I needed to decrease $i$ by $1$ inside the summation to compensate.
