# 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…

#### Solutions Collecting From Web of "What is the asymptotic bound for this recursively defined sequence?"

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)$.

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.