Intereting Posts

Different models of ZF disagree on equality of explicit recursively enumerable sets
Possibility to simplify $\sum\limits_{k = – \infty }^\infty {\frac{{{{\left( { – 1} \right)}^k}}}{{a + k}} = \frac{\pi }{{\sin \pi a}}} $
Evaluate the improper integral
Maximize trace of matrix equation given two constraints
A question regarding Frobenius method in ODE
If I generate a random matrix what is the probability of it to be singular?
How can I learn to “read maths” at a University level?
Small primes attract large primes
Deeply confused about $\sqrt{a^5}=(a^5)^{1/5}$
Smallest example of a group that is not isomorphic to a cyclic group, a direct product of cyclic groups or a semi direct product of cyclic groups.
Exercise about prime ideals
Is $\lor$ definable in intuitionistic logic?
Proving $\mathbb{Q} = \{f(\sqrt{2}): f(x) \in \mathbb{Q}\} = \{x+y\sqrt{2}:x,y\in\mathbb{Q}\}$
Combinatorial identity's algebraic proof without induction.
Proving that an additive function $f$ is continuous if it is continuous at a single point

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?

- Representing a number as a sum of k pth powers
- Big O Notation “is element of” or “is equal”
- Convert a Pair of Integers to a Integer, Optimally?
- Algorithm to generate an uniform distribution of points in the volume of an hypersphere/on the surface of an hypersphere.
- How to Solve this Boolean Equations?
- About the asymptotic formula of Bessel function
- Asymptotic behavior of $|f'(x)|^n e^{-f(x)}$
- Implementation of Monotone Cubic Interpolation
- Computing irrational numbers
- What would be the shortest path between 2 points when there are objects obstructing the straight path?

Hmm, possibly another way of heuristics is instructive.

First write the undisputable elements of the sequence:

$$\begin{array} &

a(1) &=&a(2^0) & = & 1 \\\

a(2)&=&a(2^1) &=&10 &= & 2^3 + 2*1 &=& 2*(4^1+1) \\\

a(4)&=&a(2^2) &=&84 &=& 4^3 + 2*10 &=& 4*(4^2+4^1+1) \\\

a(8)&=&a(2^3) &=&680 &=& 8^3 + 2*84 &=& 8^3+2*4^3+4*2^3+8*1^3\\\

& & & & &=& 8*(4^3+4^2+4^1+1) \\\

\ldots &=&a(2^k)&=& \ldots

\end{array} $$

It is obvious how this can be continued, because at the exponent *k* we get always $8^k$ plus two times the previous, thus the weighted sum of all powers of *8* which can be expressed as consecutive powers of *4*:

$$ a(2^k) = 2^k*(4^k+4^{k-1} \ldots +4^0)= 2^k*\frac{4^{k+1}-1}{4-1} $$

Now the step “divide” can be taken: the above gives also a meaningful possibility for interpolation of the non-explicitely defined elements. If we allow base-*2* logarithms for *k* we get for

$$\begin{array} &

& a(2^k) &= & 2^k*\frac{4^{k+1}-1}{4-1} \\\

& &= & 2^k*\frac{4*(2^{k})^2-1}{3} \\\

\text{assuming }& k&=& \frac{\log(n)}{\log(2)} \\\

& a(n) &=& n*\frac{4*n^2-1}{3} \\\

& &=& n^3 + \frac{(n-1)n(n+1)}{3!} \\\

& &=& n^3 + 2*\binom{n+1}{3} \\\

\end{array} $$

where the expression in the fourth line is the same as Fabian’s result.

The homogeneous part of the equation $T(n) =2 T(n/2)$ has the general solution $$T_0(n) = C n.$$ So all what we have to do is find a particular solution of the inhomogeneous equation $$T(n) = 2 T(n/2) + n^{3} .$$ Quite often it is good to try an ansatz which has the same form as the inhomogeneous term. Therefore, we try $T_p(n) = c n^3$ which yields $$c n^3 = \frac{c}{4} n^3 + n^3.$$ Solving for $c$, we get the particular solution $T_p(n)= \frac{4}{3} n^3$.

The general solution therefore has the form $T(n) =T_0(n) + T_p(n)$. With the initial condition $T(1)=1$, we obtain $C= – \frac{1}{3}$. So the solution is given by

$$ T(n) = \frac{n}{3} (4 n^2 -1). $$

Use Akra-Bazzi which is more useful than the Master Theorem.

Using Akra-Bazzi, I believe you get $$T(x) = \theta(x^3)$$

You can also use the Case 3 of Master theorem in the wiki link above. (Note: That also gives $\theta(x^3)$.)

There is another closely related recurrence that admits an exact

solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives

$T(1)=1$)

$$T(n) = 2 T(\lfloor n/2 \rfloor) + n^3.$$

Furthermore let the base two representation of $n$ be

$$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following **exact**

formula for $n\ge 1$

$$T(n) = \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.$$

Now to get an upper bound consider a string of one digits which yields

$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor}

2^j \left(

\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}

\right)^3.$$

Note that this bound is attained and cannot be improved. It simplifies

to

$$\frac{32}{3} 8^{\lfloor \log_2 n \rfloor}

– 24 \times 4^{\lfloor \log_2 n \rfloor}

+ \left(6 \lfloor \log_2 n \rfloor + \frac{40}{3}\right)

\times 2^{\lfloor \log_2 n \rfloor} + 1.$$

The lower bound is for the case of a one digit followed by a string of

zeros and yields

$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor}

2^j \left(

2^{\lfloor \log_2 n \rfloor-j}

\right)^3.$$

It simplifies to

$$\frac{4}{3} 8^{\lfloor \log_2 n \rfloor}

– \frac{1}{3} 2^{\lfloor \log_2 n \rfloor}$$

and this matches the results posted by the other contributors.

Joining the dominant terms of the upper and the lower bound we obtain

the asymptotics

$$2^{3 \lfloor \log_2 n \rfloor}

\in \Theta\left(2^{3 \log_2 n}\right)

= \Theta\left(n^3\right).$$

These are both in agreement with what the Master theorem would produce.

This MSE link has a series of similar calculations.

- Is there a real-valued function $f$ such that $f(f(x)) = -x$?
- Norm is weakly lower semicontinuous
- Prove by induction Fibonacci equality
- Using Fermat's little theorem
- Other challenging logarithmic integral $\int_0^1 \frac{\log^2(x)\log(1-x)\log(1+x)}{x}dx$
- Graph theory software?
- Question about the definition of a semialgebra
- Geometric interpretation of mixed partial derivatives?
- Why is the expected number coin tosses to get $HTH$ is $10$?
- Tight sequence of processes
- Finding the Moment Generating function of a Binomial Distribution
- How prove this nice limit $\lim\limits_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$
- Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?
- Why the Riemann hypothesis doesn't imply Goldbach?
- Not a small, not a big set