Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given the following recurrence:

$T(n) := T(n-k) + T(n-1),\ n,k \in N$

$T(l) := 1,\ l \in \{0,...,k-1\}$

I need to find a lower bound for $T(n)$. (For $k = 2$, the recurrence is equal to the Fibonacci recurrence where there is a closed form). In principle, $\alpha^n$ is an estimation for $T(n)$, where $\alpha$ is the first real unique root of the equation

$x^{k} - x^{k-1} - 1 = 0.$

However, testing the method numerically, it seems that $a^{n-m} \leq T(n)$ is only true for some offset $m$, with $m \geq 0$ being a natural number. I suspect $m=k$, but I do not understand the underlying math well enough...

Does someone have an idea?

Many thanks in advance.

share|cite|improve this question
I actually got the equation which defines $\alpha$ wrong. It is $x^k-x^{k-1}-1=0$... – dsd Jan 8 '13 at 20:12
You can edit the post so that anyone who doesn't read the comments doesn't get confused by your equation. – Clayton Jan 8 '13 at 20:15
The largest root gives an approximation to $T(n) / T(n - 1)$, so the real bound should be $T(n) \approx c \alpha^n$ – vonbrand Feb 6 '14 at 15:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.