Solving recurrence relations with characteristics root method

Question

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.

Answer 1

The method of characteristic polynomial is applicable to linear recurrences. Your recurrence is nonlinear.

Hint: Consider $h(n)=\log_2 g(n)$.

Answer 2

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}$$

Answer 3

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.