How can I solve the following recurrence relation?$$ f(n) = f(n-1) + f(n - \log n)$$
Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$
untagged
@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)}$.