Recurrence Problem $$A(n) = A(n/3) + A(n/2) + A(2n/3) + O(n)$$
So I am trying to solve this equation. I let $A(n) = O(n)$. I then solved the equation this way:
$$n/3 + n/2 + 2n/3 + kn,$$
which can simplify to $3n/2 + kn$, which is $cn$, where $k$ and $c$ are some constants. 
Is this the right way to do this? Thank you. 
 A: Write $A(n):=n f(n)$. Then the new unknown function $f$ would have to satisfy
$$f(n)={1\over3}f\Bigl({n\over3}\Bigr)+{1\over2}f\Bigl({n\over2}\Bigr)+
{2\over3}f\Bigl({2n\over3}\Bigr)+O(1)\qquad(n\to\infty)\ .$$
To get a counterexample to the OP's conjecture we look for a function $f$ satisfying the exact equation
$$f(n)={1\over3}f\Bigl({n\over3}\Bigr)+{1\over2}f\Bigl({n\over2}\Bigr)+
{2\over3}f\Bigl({2n\over3}\Bigr)\qquad (n>0)\ .$$
The "Ansatz" $f(n):=n^\alpha$ for an $\alpha$ to be determined results in the equation
$$1\ =\ {1\over3}\Bigl({1\over3}\Bigr)^\alpha+{1\over2}\Bigl({1\over2}\Bigr)^\alpha+{2\over3}\Bigl({2\over3}\Bigr)^\alpha\ =:p(\alpha)$$
for the exponent $\alpha$. Plotting $\alpha\mapsto p(\alpha)$ one sees that this equation has a solution $\alpha_0\doteq 0.640625>0$.
This shows that the function $A(n)\ :=\ n^{1+\alpha_0}$ is a function that satisfies the given estimate, but is not $O(n)$ $\ (n\to\infty)$.
${\bf Edit:}\ $ Of course one could have started right away with the "Ansatz" $A(n):=n^\beta$ for a $\beta$ to be determined.
