Consider the following recursive relation and its base cases: $$G_n=G_{n-1}+2G_{n-2}+G_{n-3}$$ $$G_2=4,\text{ }G_1=2,\text{ }G_0=1$$ The question asks which of the following is the best solution to the aforementioned relation:
$A)\text{ }G_n\le4^n$
$B)\text{ }G_n\le2^{n+1}$
The correct answer is $A$ and the book provides the solution below:
We have that $G_{n-1}+2G_{n-2}+G_{n-3}\lt G_{n-1}+2G_{n-1}+G_{n-1}$, hence $G_n\lt 4G_{n-1}$ which is the same thing as $G_n\lt 4^n$.
It is understandable that the solution above is an upper bound, however choice $B\text{ }(G_n\lt 2^{n+1})$ also holds true until around $n=12$ I guess.
So I have a few questions:
1- How can I make sure that for example choice $B$ is not an upper bound, in an easy way? testing for big $n$'s by hand would be very time consuming.
2- Is there a way to find the least upper bound (for example for the recursive relation in question) without actually solving the relation?