# 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.

• Note: $g(n)=(g(n-1)^3)/(2(g(n-2)^2))$ is not linear so this method will not work. However, there is a closelly related one that is linear which you can use for this. – GEdgar Jul 23 '19 at 12:00

## 3 Answers

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

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

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

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.