6

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.

dsd
  • 161
  • 1
    I actually got the equation which defines $\alpha$ wrong. It is $x^k-x^{k-1}-1=0$... – dsd Jan 08 '13 at 20:12
  • 2
    You can edit the post so that anyone who doesn't read the comments doesn't get confused by your equation. – Clayton Jan 08 '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 06 '14 at 15:36

0 Answers0