# Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(x) &= \begin{cases} f(x-1) + g(x/2) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \end{align*}

By induction, $f(x)$ can be expressed non-recursively as a sum over $g$. That can be substituted into the definition of $g$ to get a single recursion, which can be compared to a well-known standard recurrence to show a lower bound. Finally, the comparison is close enough to hint that the upper bound must be similar to the lower bound, so you should be able to guess an upper bound and prove it.