Proving that the closed form of a recurrence is positive infinitely often. $$[-1, 1, 7, 17, 23, 1, -89, -271, -457, -287, 967, 4049]$$
are the first couple of terms in the recurrence $h(n) = 3h(n-1) - 4h(n-2)$, where $h(1) = -1$ and $h(2) = 1$. It seems that the recurrence's terms are positive infinitely often. How can I prove this?
I have tried to suppose that the recurrence's terms are always negative after a point $n-1$, in which case it must be true that
$h(j) < 0 \iff |3h(j-1)| > |4h(j-2)| \iff |h(j-1)| > \frac{4}{3}|h(j-2)|$ for all $j \geq n$
 A: One possibility is to explicitly solve the recurrence.  See for example page 79 of these notes by Miguel Lerma, under "complex roots", for the general solution. The roots of the characteristic equation $r^2 - 3r + 4 = 0$ are $r = (3 \pm \sqrt{-7})/2$, or $r = 2e^{\alpha i}$ where $\alpha = \tan^{-1} (\sqrt{7}/3) = \cos^{-1} (3/4)$.  Therefore you have
$$ h(n) = 2^n (k_1 \cos n\alpha + k_2 \sin n\alpha) $$
for some (real) constants $k_1$ and $k_2$ which can be found explicitly.  Now you just need to show that $k_1 \cos n\alpha + k_2 \sin n\alpha$ is positive infinitely often.
A: Let's first notice that if $h(n), h(n-1) < 0$ and $h(n)\geq h(n-1)$, we will have $$h(n+1) = 3h(n)-4h(n-1)\geq 3h(n-1)-4h(n-1) = -h(n-1) > 0$$ This implies that once the sequence becomes increasing, it becomes positive on the next term. Now let's prove that the sequence, once it becomes negative, always increases at some point. For $h(n+1) < h(n)$ to be satisfied, we need $$3h(n)-4h(n-1) < h(n) \Leftrightarrow h(n) < 2h(n-1)$$ For $h(n) < 2h(n-1)$ to be satisfied, we need $$3h(n-1)-4h(n-2) < 2h(n-1) \Leftrightarrow h(n-1) < 4h(n-2)$$ For $h(n-1) < 4h(n-2)$ to be satisfied, we need $$3h(n-2)-4h(n-3) < 4h(n-2) \Leftrightarrow h(n-2) > -4h(n-3)$$ so for $h(n+1) < h(n)$, either $h(n-3)$ or $h(n-2)$ is positive. Once both $h(n-3)$ and $h(n-2)$ are negative, we necessarily have $h(n+1)\geq h(n)$, which implies that $h(n+2)$ will be positive. Therefore, at least $1/6$ of all terms will be positive, since at least one of the terms in $\{h(n-3), h(n-2), h(n-1), h(n), h(n+1), h(n+2)\}$ will be positive. Note that this is irrespective of initial conditions.
