1

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

Muno
  • 1,509

2 Answers2

1

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.

Michael Lugo
  • 22,354
  • as the argument is about $41^\circ$ or about $360^\circ/8.7,$ the real part will be positive for either four or five in a row, then negative for four or five in a row, with a cycle usually being nine turns. – Will Jagy Jul 24 '17 at 18:35
  • Very nice. Namely, $n\alpha\bmod 2\pi$ will be equidistributed in $[0, 2\pi)$ due to the irrationality of $\alpha/2\pi$, so as long as there is a subset of $[0, 2\pi)$ of positive measure where $k_1\cos(n\alpha)+k_2\sin(n\alpha)$ is positive, the result follows (and the proportion of positive terms will be determined by the measure of this subset divided by $2\pi$). – Michael L. Jul 24 '17 at 18:40
  • Since $k_1 \cos (n\alpha) + k_2 sin (n\alpha)$ can be expressed as a single (phase-shifted) sine, that proportion is just $1/2$. – Michael Lugo Jul 24 '17 at 18:46
  • Examining the first 1,000 terms in Mathematica bears this out. Almost exactly half of them are positive. – Michael L. Jul 24 '17 at 19:04
  • Is this true of any recurrence for which the characteristic equation has complex roots, then? – Michael L. Jul 24 '17 at 19:19
  • If $\alpha/2\pi$ is rational there might be some extra conditions. For example, in the case of $h(n) = h(n-1) - h(n-2)$, with $h(1) = 0, h(2) = 1$, the characteristic equation's roots are the primitive sixth roots of unity and $h(n)$ is periodic with period 6. But the sequence is $(0, 1, 1, 0, -1, -1, \ldots)$ repeating, so if you count zeroes as half positive and half negative you can probably rescue the result that way. – Michael Lugo Jul 24 '17 at 19:31
1

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.

Michael L.
  • 5,521