How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?
Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.

For large $n$, we have roughly $S(n) - S(n-1) \approx S'(n)$, and so we are led to solve the differential equation
$$
S'(n) = S(n/2).
$$
Consider $f(n) = \exp (\tfrac{1}{2}\log_2^2 n)$. Then
$$
f'(n) = \exp (\tfrac{1}{2}\log_2^2 n) \cdot \frac{\ln n}{(\ln 4)n},
$$
whereas
$$
f(n/2) = \exp(\tfrac{1}{2} (\log_2 n - 1)^2) \approx \exp(\tfrac{1}{2}\log^2 n) \exp(-\log n) = \exp(\tfrac{1}{2} \log^2 n) \cdot \frac{1}{n}.
$$
This suggests that, at the very least, $\ln S(n) = \Theta(\log^2 n)$.

Where does this come from? You can think of $S(n)$ (with an appropriate base case!) as the number of ways to go from $n$ to zero by applying two operations: subtract 1 and divide by 2. A "typical" such sequence will contain roughly $\log_2n$ many operations of the second type, out of $\Theta(n)$ operations in total, leading to the very rough estimate $\binom{\Theta(n)}{\log_2 n}$, which is also of the form $\exp \Theta(\log^2 n)$.



Consider for concreteness the following precise definition of $S(n)$: the base case is $S(0) = 1$, and for $n &gt; 0$,
$$
S(n) = S(n-1) + S(\lfloor n/2 \rfloor).
$$
This is sequence A000123. Knuth, An almost linear recurrence, showed that
$$
\log_4 S(n) \sim \log_4^2 n,
$$
that is, the ratio of the two terms tends to 1 as $n \to \infty$. The OEIS entry contains even more precise asymptotics.