Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$ How can I solve the following recurrence relation?
$$ f(n) = f(n-1) + f(n - \log n)$$
@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$

To see the lower bound, apply the recurrence definition $\log n$ times, to get $$f(n) = 2f(n - \log n) + f(n - \log n - 1) + \ldots + f(n - 2 \log n) \ge \log n \cdot f(n - \log n) \ .$$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{\Omega(n \log \log n / \log n)}$.

To get the upper bound, use the recurrence $\log n$ times and get that $$f(n) \le (\log n + 1) \cdot f(n - \log n) \ . $$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{O(n \log \log n / \log n)}$.