2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – GEdgar Jul 23 '19 at 12:00
1
$\begingroup$

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.