# What is the asymptotic bound for this recursively defined sequence?

$f(0) = 3$

$f(1) = 3$

$f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$

Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not be able to prove it...

-

In your recurrence, set $n=4m$ for an integer $m$. Then $f(4m) = f(2m)+f(m) + 4 c m$. From your original equation, it's easy to determine $f(1) = 3$, $f(2) = 6 + 2c$, $f(4) = 9 + 6 c$.

Now, let $g(n) = f(2^n)$, so the equation translates into $g(n+2) = g(n+1) + g(n) + c 2^{n+2}$. The solution to this equation is easy to find. $$g(n) = c_1 F_n + c_2 L_n + c 2^{n+2}$$ where $F_n$ are Fibonacci numbers, and $L_n$ are Lucas numbers. Asymptotically, Fibonacci and Lucas numbers grow only as $\phi^n$, and since $\phi < 2$, the dominating term is $c 2^{n+2}$. Rolling back, $f(m) \sim 4 c m + o(m)$.

-
I'm not sure if you can just say "rolling back" like that here. From computing $g(n)$ out to $2^{10}$ (which I admit isn't that far) it seems like $f(2^n) \sim c 2^{n+2}$ as $n \to \infty$ but, say, $f(3 \times 2^n)$ isn't necessarily approaching $c (3 \times 2^{n+2})$. Is there some theorem encapsulated in the phrase "rolling back" that I'm unaware of? –  Michael Lugo Oct 1 '11 at 19:32
@MichaelLugo Well, let $h(n) = f(3 \times 2^n)$, then $h(n+2) = h(n+1) + h(n) + 3 c 2^n$ just as well, and $h(n) \sim 4 c ( 3 \times 2^n)$, so the result would hold. You may ask what about $f(3^n)$, but I suspect the story will turn out the same by some regularity of the solution, but I do not have a satisfactory answer for this. –  Sasha Oct 1 '11 at 20:00
Suppose we first study $$g(n) = f(n)-3$$ which has $g(0)=g(1)=0$ and $$g(n) = g(\lfloor n/2 \rfloor) + g(\lfloor n/4 \rfloor) + cn+3.$$ Then it is not difficult to see that for the binary representation of $n$ being $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ we have that for $n\ge 2,$ $$g(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right)$$ which in turn implies $$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} [z^j] \frac{1}{1-z-z^2} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right).$$ Now note that the polynomial term is the generating function of the Fibonacci numbers shifted down by one, so that this simplifies to an attractive exact formula for all $n$ which is $$f(n) = 3 + \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \left(3 + c\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}\right) = 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
Next we compute upper and lower bounds. For an upper bound consider a string of one digits, which gives the following bound which is actually attained and cannot be improved upon: $$f(n) \le 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\ = 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j}-1) \\= c + (3-c) F_{\lfloor \log_2 n \rfloor+2} + c 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j}.$$ Now the sum term converges to a limit. We have $$\sum_{j=0}^\infty F_{j+1} 2^{-j} = \frac{1}{\sqrt{5}} \left(\varphi \sum_{j=0}^\infty (\varphi/2)^j - (-1/\varphi) \sum_{j=0}^\infty (-1/\varphi/2)^j\right) \\ = \frac{1}{\sqrt{5}} \left(\frac{\varphi}{1-\varphi/2}+\frac{1/\varphi}{1+1/\varphi/2}\right) =4.$$ For a lower bound consider a one followed by a string of zeros, giving $$f(n) \ge 3 F_{\lfloor \log_2 n \rfloor+2} + c \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{\lfloor \log_2 n \rfloor-j} =3 F_{\lfloor \log_2 n \rfloor+2} + c 2^{\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j}.$$ The sum term converges to four as before. We see that the dominant asymptotics in both bounds come from the two terms $$F_{\lfloor \log_2 n \rfloor+2} \quad\text{and}\quad 2^{\lfloor \log_2 n \rfloor}.$$ Note that $$F_n \sim \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$$ which means that the power of two dominates, giving a final complexity of $$\Theta\left(2^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2 n}\right) = \Theta(n).$$ This MSE link points to a similar calculation.