I am trying to understand the solution to the following recurrence. $I(n) = 1+n/B$ if $n \leq \alpha M$ and $I(n) = 4I(n/2)+1$ otherwise.
The solution, according to the paper this is from, is $I(n) = 1+n/B+n^{2}/(BM)$. The authors provide no proof and it does not appear correct to me, and solving the recurrence explicitly, I obtained $I(n) = n^{3}/(\alpha^{2}M^{2}B)$. I am not sure who is wrong, so any help is appreciated.
Note: $\alpha$ may be assumed to be a constant, i.e. 1. However, $B$ and $M$ are variables that must be included in the final answer.
When $n = \alpha M$ we have $I(\alpha M)=1+\alpha\frac MB$. Now regarding
$$ I(n) = 4 I\left(\frac n2\right)+1 $$
making $n= 2^m$ we have $I\left(2^m\right) = 4 I\left(2^{m-1}\right)+1$. This recurrence can be recasts as
$$ r(m) = 4r(m-1)+1 $$
with solution
$$ r(m) = \frac 13(4^m-1)+ c_0 4^{m-1}\ \ \ \ \ \ \ (1) $$
now taking $m = \log_2 n$ we have
$$ I(n) = \frac 13(4^{\log_2 n}-1)+ c_0 4^{\log_2 n-1} = \frac{1}{12} \left((3 c_0+4) n^2-4\right) $$
such that $I(\alpha M)=1+\alpha\frac MB$ so we have
$$ c_0 = \frac{4}{3} \left(\frac{3 \alpha M+4 B}{\alpha ^2 B M^2}-1\right) $$
and finally
$$ I(n) = \frac{1}{3} \left(\frac{n^2 (3 \alpha M+4 B)}{\alpha ^2 B M^2}-1\right) $$
NOTE
As $(1)$ is a linear recurrence it can be solved as follows:
$$ \cases{ r_h(m) = 4 r_h(m-1)\\ r_p(m) = 4 r_p(m-1) + 1 \\ r(m) = r_h(m) + r_p(m) } $$
now, the solution for the homogeneous is
$$ r_h(m) = c_04^{m-1} $$
now choosing a particular such that $r_p(m) = c_0(m)4^m$ after substitution we obtain
$$ c_0(m)4^m = c_0(m-1)4^m + 1\Rightarrow c_0(m) = c_0(m-1) + \frac{1}{4^m} $$
hence $c_0(m) = \sum_k \frac{1}{4^k} = \frac{1-4^{-m}}{1-4^{-1}}= \frac 134(1-4^{-m})$ and $r_p(m) = \frac 13(4^m-1)$