Solving recurrence relations with characteristics root method I am able to solve more simple recurrences using this method, however I was given a problem that I can’t seem to work out. I think my mistake is in forming the characteristic polynomial but I’m not sure. 
The recurrence is: $g(0) = 2, g(1) = 16, g(n)=\frac{g(n-1)^3}{2g(n-2)^2}$
I get the characteristics polynomial as $r^n = \frac{r^3(n-1)}{2r^2(n-2)}$ which simply gives the results $r=2$. But the usually steps from here don’t give a correct closed form.
I think my characteristics polynomial is wrong as I’ve never had to deal with the recurrence being a fraction or the fact they are to different powers. I would be grateful if someone could explain how to obtain the correct one and if there are any tricks to solving recurrences like this.
 A: The method of characteristic polynomial is applicable to linear recurrences. Your recurrence is nonlinear.
Hint: Consider $h(n)=\log_2 g(n)$.
A: As it was mentioned, straight application of characteristic polynomial method won't work.
However, you can apply a trick
$$g(n)=\frac{g(n-1)^3}{2g(n-2)^2} \iff \frac{g(n)}{g(n-1)}=\frac{1}{2}\cdot \left(\frac{g(n-1)}{g(n-2)}\right)^2$$
If you note $a(n)=\frac{g(n)}{g(n-1)}$, with $a(1)=\frac{16}{2}=8=2^3$, this is
$$a(n)=\frac{a(n-1)^2}{2}=
\frac{a(n-2)^4}{2^3}=
\frac{a(n-3)^8}{2^7}=
\frac{a(n-k)^{2^k}}{2^{2^k-1}}=...\\
=\frac{a(1)^{2^{n-1}}}{2^{2^{n-1}-1}}=
2^{3\cdot2^{n-1}-2^{n-1}+1}=2^{2^n+1}$$
which you can show simply using induction. After, solve for the $g(n)$ from
$$g(n)=g(n-1)\cdot 2^{2^n+1}$$
A: Another method is the substitution method. This method is straightforward, but might require a lot of calculations for such a recurrence.
Using this method, you could substitute the $f(n)$ on the right-hand-side with the right-hand-side of $f(n)$. You could do this for about 3 or 4 times until you see a pattern, which you can describe by any variable, such as $i$, where $i$ is the amount of substitutions. When you have described the pattern using $i$, you could express $i$ as an equation that makes the argument of the function equal to 0. Now, substitute all $i$'s with the right-hand-side of $i$, and you should then have a solution.
