<p>@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$</p>

<p>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)}$.</p>

<p>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)}$.</p>

CC BY-SA 3.0
2016-01-29T16:30:41.887Z
2016-01-29T16:30:41.887Z
greg
<p>How can I solve the following recurrence relation?
$$ f(n) = f(n-1) + f(n - \log n)$$</p>

CC BY-SA 3.0
2016-01-29T03:00:01.937Z
What do you get if you try $f(n) = 2f(n - \log n)$? It appears that you will get a lower bound of $2^{\Omega(n/\log n)}$.
Chandra Chekuri
CC BY-SA 3.0
2016-01-29T03:14:49.987Z
@ChandraChekuri Oh, that's great! And there's an upper bound of $2^{O(n \log \log n / \log n)}$: we use the recurrence $\log n$ times, and get that $f(n) \le (1 + \log n) f(n - \log n)$. Then we apply this $n / \log n$ times and get $f(n) \le (1 + \log n)^{n / \log n} = 2^{O(n \log \log n / \log n)}$. So the gap between the upper bound and lower bound is only $\log \log n$ in the exponent. This is actually enough for my purposes, but I'll leave the question open in case someone wants to and is able to close the gap. Thank you very much, Chandra!
greg
CC BY-SA 3.0
2016-01-29T12:04:48.373Z
Well, the same trick gives $f(n)\ge(\log n)f(n-2\log n)$, so $f(n)=2^{\Theta(n\log\log n/\log n)}$.
Emil Jeřábek
<recursion>
Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$
greg
# Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

(Asked by: username_0 on 2016-01-29)

How can I solve the following recurrence relation?
$$ f(n) = f(n-1) + f(n - \log n)$$

**Tags:** recursion
> **Comments:**
> **username_1**: What do you get if you try $f(n) = 2f(n - \log n)$? It appears that you will get a lower bound of $2^{\Omega(n/\log n)}$.  
> **username_0**: @ChandraChekuri Oh, that's great! And there's an upper bound of $2^{O(n \log \log n / \log n)}$: we use the recurrence $\log n$ times, and get that $f(n) \le (1 + \log n) f(n - \log n)$. Then we apply this $n / \log n$ times and get $f(n) \le (1 + \log n)^{n / \log n} = 2^{O(n \log \log n / \log n)}$. So the gap between the upper bound and lower bound is only $\log \log n$ in the exponent. This is actually enough for my purposes, but I'll leave the question open in case someone wants to and is able to close the gap. Thank you very much, Chandra!  
> **username_2**: Well, the same trick gives $f(n)\ge(\log n)f(n-2\log n)$, so $f(n)=2^{\Theta(n\log\log n/\log n)}$.  

---

## 1 answers

### Answer by username_0 on 2016-01-29. Score: 14 | Accepted answer

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


---

