From what I know the Tribonacci sequence is given by:
T(n) = T(n-1) + T(n-2) + T(n-3)
My book says that "We can show by induction that for large enough n, the Fibonacci numbers satisfy the inequality (1.6)n < F(n) < (1.7)n."
Which of these four functions is the largest that is eventually smaller than T(n)?
Select one:
a. $(1.9)^n$
b. $2^n$
c. $(1.7)^n$
d. $(1.8)^n$
I am not looking for the answer but for way to approach this. I am confused by what is actually asking.
I can show the powers of $2$ grow faster than $T(n)$.
If I start off $T(n-3)=2^{n-3},T(n-2)=2^{n-2},T(n-1)=2^{n-1}$ then $$T(n)=T(n-1)+T(n-2)+T(n-3)=\frac{2^n}2+\frac{2^n}4+\frac{2^n}8=\frac782^n$$ So $T(n)$ has started to lag behind powers of $2$.
On the other hand, if I start them off $T(n-1)=1.5^{n-1}$, and so on, I find that $$T(n)=\frac{1.5^n}{1.5}+\frac{1.5^n}{1.5^2}+\frac{1.5^n}{1.5^3}>1.5^n$$ so $T(n)$ has started to leap ahead of $1.5^n$