Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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 at 15:36

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.