# On a mistake in a derivation regarding a recurrence relation.

Suppose we have a sequence $$\{u_t \}_{t \in \mathbb{N}}$$ given by the recurrence relation $$u_{t+1} = q_0 u_t + q_1 u_{t-1} + \dots + q_p u_{t-p} + \epsilon, \quad \epsilon >0$$ where $$p \in \mathbb{N}$$ and $$q_1, \dots, q_p$$ are such that the roots $$r_0,r_1, \dots, r_p$$ of the associated homogeneous characteristic equation $$r^{p+1} - q_0 r^p - q_1 r^{p-1}- \dots - q_p = 0$$ lie inside the unit circle and the sequence is strictly positive.

We can render the sequence homogeneous by settting $$u^* = \epsilon / (1 - q_0 - q_1 - \dots -q_p)$$ and noticing that $$(u_{t+1} -u^*) = q_0 (u_t - u^*) + q_1 (u_{t-1} - u^*) + \dots + q_p (u_{t-p} - u^*)$$ It is known that the solution to this recurrence will have the form $$u_{t+1} - u^* = a_0 r_0^{t+1}+a_1 r_1^{t+1}+ \dots + a_p r_p^{t+1}$$ where $$a_0,a_1, \dots, a_p$$ are real numbers and $$r_0, r_1, \dots , r_p$$ are the roots of the characteristic equation. Taking the limit for $$t \rightarrow \infty$$ and recalling that the roots where assumed inside the unit circle we obtain that $$\lim_{t \rightarrow \infty} u_{t+1 } = u^*$$ but (it seems to me) $$u^*$$ can be negative and the sequence was taken strictly positive. Where is the mistake?

Edit: The Eneström–Kakeya theorem (see this link) seems to imply that we can construct a polynomial with all roots inside the unit circle and such that $$u^* = \epsilon / (1 - q_0 - q_1 - \dots -q_p)$$ is negative. So I still have a doubt if this derivation is correct, thus I am putting a bounty on the question.

• The general solution of the homogeneous equation will only have the form you mentioned if all roots of the characteristic polynomial are real and have multiplicity one. However, this is not relevant to the question because all these terms would go to zero ans $t \to \infty$. Why do you say that $u^*$ can be negative? When you are building the solution you are never using the positivity requirement, so your result holds regardless of that condition. Presumably, if the positivity assumption holds, $u^*$ will in fact be positive. Feb 8 '19 at 9:44
• @PierreCarre First off thank you for your answer! So for a polynomial with all positive coefficients $q_0, \dots, q_p$ and roots inside the unit circle it will hold that $q_0 + \dots + q_p < 1$ ? Feb 8 '19 at 10:43
• What I'm guessing (did not check) is that if $u_t >0, \forall t$ and $p(\lambda)$ has all its roots inside the unit circle, then we have that $\frac{\varepsilon}{1- \sum q_i} \ge 0$. If $\varepsilon > 0$ this means that $\sum q_i < 1$. Feb 8 '19 at 10:47

Under the given assumptions, we can show that $$u^*>0$$. We can observe that $$1-q_0-q_1-\cdots -q_p = p(1)$$ where $$p(r) = r^{p+1}-q_0r^p-q_1r^{p-1}-\cdots -q_p$$ is the characteristic polynomial. Note that $$\lim\limits_{r\to\infty}p(r) =\infty$$. If $$p(1)< 0$$, then by the intermediate value theorem, there exists $$r_0\in(1,\infty)$$ such that $$p(r_0)=0$$. Since we are assuming that every root of $$p(r)$$ lies in the open unit disk, this leads to a contradiction. Thus we have $$p(1)> 0$$ as $$p$$ cannot have $$1$$ as a root. As a result, we get $$u^* =\frac{\epsilon}{p(1)}>0$$.