Simplify a recursively defined function in Maple I have the following problem. Out of the runtime analysis of an divide and conquer algorithm I got the following formula for the necessary flops: 
flops(n): = (89+1/3)*n^3 + 2 * flops(n/2)

and 
flops(1):= 0 

I want to sum it up and to remove the recursion with Maple. But I do not get it working. Everytime Maple complains: Error, (in flops) too many levels of recursion
How can this be done? 
 A: We can actually do a little more and find an exact solution to this recurrence. First solve for $S(n)$ where $S(0)=0$ and $$S(n) = 268/3 n^3 + 2 S(\lfloor n/2\rfloor).$$
Let $$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n.$
By inspection we see that
$$ S(n) = 268/3 \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j
\left(\sum_{k=j}^{\lfloor\log_2 n\rfloor}  d_k 2^{k-j}\right)^3.$$
This formula is exact.
We are interested in $T(n)$ which has the same recurrence as $S(n)$ but with $T(1)=0.$ (We have $S(1)=268/3.$) So this gives
$$T(n) = -268/3 \times 2^{\lfloor\log_2 n\rfloor} + 268/3 \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j
\left(\sum_{k=j}^{\lfloor\log_2 n\rfloor}  d_k 2^{k-j}\right)^3.$$ This formula is exact, too.
To do the asymptotics we need upper and lower bounds. An upper bound occurs for a string of one digits, giving
$$T(n) \le 
268/3 \left(32/3\times 2^{3\lfloor\log_2 n\rfloor} -24\times 2^{2\lfloor\log_2 n\rfloor}
+ 37/3 \times 2^{\lfloor\log_2 n\rfloor} + 
6\lfloor\log_2 n\rfloor 2^{\lfloor\log_2 n\rfloor} +1\right).$$
We get the lower bound by considering a one followed by a string of zeros, giving
$$T(n) \ge 268/3
\left(4/3 \times 2^{3\lfloor\log_2 n\rfloor} 
- 4/3 \times 2^{\lfloor\log_2 n\rfloor}.\right).$$ 
If we put $m = 2^{\lfloor\log_2 n\rfloor}$ this becomes
$$ 268/3
\left(4/3 \times m^3 - 4/3 \times m\right) =
1072/9 \; m \; (m^2-1),$$
which is the result that acer computed in his post. 
The asymptotically dominant terms are
$$ 268/3 \times 32/3\times 2^{3\lfloor\log_2 n\rfloor} \quad \text{and} \quad
268/3 \times 4/3 \times 2^{3\lfloor\log_2 n\rfloor},$$
so that $$T(n) \in \Theta\left(2^{3\lfloor\log_2 n\rfloor}\right) =
\Theta\left(2^{3\log_2 n}\right) = \Theta(n^3),$$
in accordance with the Master theorem.
A: Are you intending that n and integer and a power of 2?
restart:

Flops:=proc(N::rational)
   if N<=1 then return 0;
   else (89+1/3)*N^3+2*procname(N/2);
   end if;
end proc:

seq(Flops(2^i), i=0..4);

           0, 2144/3, 21440/3, 60032, 1457920/3

G:=unapply(rsolve({flops(n)=(89+1/3)*n^3+2*flops(n/2),flops(1)=0},
                  flops),
           n);

                                           2
                      G := n -> 1072/9 n (n  - 1)

seq(G(2^i), i=0..4);                                                

           0, 2144/3, 21440/3, 60032, 1457920/3

