Upper and Lower bounds for the function

Question

Please find the upper and lower bounds of the recurrence relations.

$T(n)= 4T(n−2) + 6T(n-3) + 3^n $ if $n>=3$

$T(n)= 1 $ if $ n <=2$

I am confused. Thanks a lot :)

Answer 1

Hint

Have a look to the first terms : you have $T(0)=1$, $T(1)=1$, $T(2)=1$, $T(3)=37$ ... The next term is composed by the addition of previous positive terms plus $3^n$. So, a lower bound is clearly $3^n$ and an upper bound is infinity.

To give you an idea $$T(10)=141,787$$ $$T(20)=10,086,292,531$$ $$T(30)=613,731,130,507,819$$ $$T(40)=36,431,449,755,746,056,291$$

Added after Gerry Myerson's comment

I do not know how to prove the following. What I did was to plot $log(T(n))$ as a function of $n$ and the result is almost a straight line from which it seems that $3^{n+1}$ is an upper bound ($3^{10}=59,049,3^{11}=177,147$), ($3^{20}=3,486,784,401,3^{21}=10,460,353,203$),($3^{30}=205,891,132,094,649,3^{31}=617,673,396,283,947$), ($3^{40}=12,157,665,459,056,928,801,3^{41}=36,472,996,377,170,786,403$)

May be, considering the series defined by $U(n)=T(n)/3^n$ could help ... but the CAS I use just gave up.

Answer 2

The sequence is (starting at n=0) 1, 1, 19, 37 ,163, 505,.. It has the generating function $$\sum_{n\ge 0}T(n)x^n=\frac{1-2x+12x^2-18x^3}{(3x-1)(6x^3+4x^2-1)}$$ and follwing Binet's formula we can decompose this into partial fractions $$\ldots \frac{1}{1/3-x}-\frac{0.862..}{0.39602..-x} - \frac{0.4313..-0.716..i}{x+0.5131..+0.372..i}+cc$$. If each of these 4 terms is re-expanded in its geometric series, the bounds for large $x$ should emerge.