0
$\begingroup$

If we have a linear recurrence relation on a sequence $\{x_n\}$, then I know how to find the worst case asymptotic growth. We consider the largest absolute value $\alpha$ of any root of the characteristic polynomial. Then, independent of the initial values, the asymptotic growth is $x_n=\mathcal{O}(\alpha^n)$. I realize that sometimes you get an extra polynomial factor for roots of larger order, but let us ignore all polynomial factors for convenience.

For example if $x_n=x_{n-1}+x_{n-2}$, then $x_n=\mathcal{O}(\phi^n)$ where $\phi$ is the golden ratio, because that is the largest absolute value of any root of $x^2-x-1$.

My question is about the following. Say we have two linear recurrence relations on a sequence $\{x_n\}$ such that the first holds for some $n$, but the second holds for other $n$. For example, say we know that for all $n$ we have either $x_n=x_{n-1}+x_{n-2}$, or $x_n=2x_{n-2}+4x_{n-3}$, but we do not know which of the two holds for which values of $n$.

My intuition tells me that, to find the worst case asymptotic growth, I just have to take the worst asymptotic growth of any of the recurrences in question. In the example I just gave we hence have $x_n=\mathcal{O}(2^n)$ by the second recurrence. However, I can not come up with a rigorous argument for this to be the case. So my question is whether my intuition is correct.

For some context, I am studying branching algorithms for $NP$-hard problems. Often times you want to have multiple cases for how you should branch, which is where the multiple recurrences come from. However, there is no clear way to predict which case will pop up, and hence which recurrence holds for which index. Note that you can get arbitrarily many different linear recurrences.

$\endgroup$
1
$\begingroup$

It's not correct. A counterexample: $$x_n = \frac43x_{n-1}-\frac43x_{n-2}\quad\text{or}\quad x_n = -\frac43x_{n-1}-\frac43x_{n-2}$$ $$x_n = 1,2,-4,-8,16,32,-64,\dots$$ The sequence grows as $2^n$. The roots of the recurrences are $\dfrac{\pm 2\pm 2\sqrt{2}i}{3}$, each of absolute value $\dfrac{2}{\sqrt{3}} < 2$.

Now, your application to complexity problems should come with some positivity requirements, which would rule out this example. It might be enough to salvage things, but I can't say without further study.

OK, I've come back to it. Assume the sequence $x_n$ is positive (for $n\ge 0$) and the recurrences $x_n^{(j)}=c_1^{(j)}x_{n-1}+c_2^{(j)}x_{n-2}+\cdots+c_{k}^{(j)}x_{n-j}$ have nonnegative coefficients $c_i^{(j)}$.

In this form, each of the characteristic equations $t^k-c_1^{(j)}t^{k-1}-c_2^{(j)}t^{k-2}-\cdots - c_k^{(j)}$ has exactly one positive real root $b_j$, and this $b_j$ has the largest absolute value of any root. Let $B$ be the maximum of the $b_j$. Now, normalize: let $y_n = B^{-n}x_n$, and transform the recurrences to fit the new sequences. The new recurrences are \begin{align*}y_n^{(j)} &= B^{-1}c_1^{(j)}y_{n-1}+B^{-2}c_2^{(j)}y_{n-2}+\cdots+B^{-k}c_k^{(j)}y_{n-k}\\ y_n^{(j)} &= d_1^{(j)}y_{n-1}+d_2^{(j)}y_{n-2}+\cdots+d_k^{(j)}y_{n-k}\end{align*} with $y_n\in \{y_n^{(j)}\}$, naming the new coefficients $d_i^{(j)}$. What's the point? Since $t^k-c_1^{(j)}t^{k-1}-c_2^{(j)}t^{k-2}-\cdots-c_k^{(j)} \ge 0$ for $t\ge b_j$, it's nonnegative for $t = B$ and all $j$. After scaling by those powers of $B$, $$1-d_1^{(j)}-d_2^{(j)}-\cdots-d_k^{(j)}\ge 0$$ for all $j$. Consequently, if each of $y_{n-1},y_{n-2},\dots,y_{n-k}$ is $\le P$ for some constant $P$, so is $y_n^{(j)}$. If we take enough initial conditions to cover all of the recurrences and let $P$ be the maximum of those initial conditions, then, by induction, $y_n\le P$ for all $n$.

Multiply by $B^n$ to go back to the $x_n$, and that's it: $x_n\le PB^n$, where $P$ is some constant depending on initial conditions and $B$ is the largest root of the characteristic equations for the recurrences.

$\endgroup$
  • $\begingroup$ That is very interesting! But indeed, for my application it only becomes useful to consider positive sequences where the recurrence has only positive coefficients. Could you share some of your thought process in finding this example? $\endgroup$ – SmileyCraft Mar 21 at 20:54
  • 1
    $\begingroup$ Looking at my scratch paper ... I wrote down the sequence and fitted the recurrences to it. The signs alternating by twos were the simplest way I could get exponential growth without being an exponential, and then I needed weights to make each term contribute positively to the next. $\endgroup$ – jmerry Mar 21 at 21:00
  • $\begingroup$ Right, so that approach is not going to work for positive sequences. If $x_n=\alpha^n$ obeys a certain recurrence for some $n$, then $\alpha$ has to be a root of the characteristic polynomial. $\endgroup$ – SmileyCraft Mar 21 at 21:22
  • $\begingroup$ The positive case is true. Proof added. $\endgroup$ – jmerry Mar 21 at 22:04
1
$\begingroup$

Here is a partial answer that applies only in the special case where the $x_i>0$ and the coefficients are positive.

Suppose $k$ is a positive integer,

  1. $\{x_n | n=1,2,\ldots\}\subset\mathbb [0,\infty)$,
  2. $x_n =\sum_{i=1}^k\alpha_i x_{n-i}$ or $x_n =\sum_{i=1}^k\beta_i x_{n-i}$ for all $n>k$,
  3. the real numbers $\alpha_1, \alpha_2, \ldots, \alpha_k$ and $\beta_1, \beta_2, \ldots, \beta_k$ are all non-negative,
  4. there exists a $y\in\mathbb R$ such that $y>0$ and $y^k = \sum_{i=1}^k\alpha_i y^{k-i}$,
  5. there exists an $z\in\mathbb R$ such that $z>0$, $z^k = \sum_{i=1}^k\alpha_i z^{k-i}$, and
  6. there exists a $c\in \mathbb R$ such that $x_j\leq c \max(y^j,z^j)$ for $j=1, 2, \ldots k$.

Then (1) $x_n\leq c \max(y^n,z^n)$ for $n=1,2, \ldots$.

The proof is a rather straight forward induction assuming I did not make any mistakes.

Let $w=\max(y,z)$. Statement (1) holds for $n=1,2, \ldots k$ by hypothesis 6. Assume statement (1) holds for $n=1,\ldots, m-1$ where $m$ is a positive integer greater than $k$. Then one of the following two cases hold:

Case 1: $x_m = \sum_{i=1}^k\alpha_i x_{m-i}$, or

Case 2: $x_m = \sum_{i=1}^k\beta_i x_{m-i}$.

For Case 1, notice that for $n=1,2\ldots m-1$, $$x_n\leq c w^n = c (w/y)^n y^n\leq c (w/y)^{m-1} y^n.$$ So, $$x_m = \sum_{i=1}^k\alpha_i x_{m-i} \leq \sum_{i=1}^k\alpha_i c (w/y)^{m-1} y^{m-i}$$ $$ = c (w/y)^{m-1} y^{m} y^{-k} \sum_{i=1}^k\alpha_i y^{k-i} = c (w/y)^{m-1} y^{m} y^{-k} y^k $$ $$ = c (w/y)^{m-1} y^{m} = c w^{m-1} y \leq c w^m.$$

Using very similar reasoning, it can be shown that $x_m\leq c w^m$ in Case 2 also.

Thus by induction, hypotheses 1 to 6 imply that $x_n\leq c w^n$ for all positive integers $n$.

$\endgroup$
  • $\begingroup$ It looks like I wrote pretty much the same thing as jmerry. :) $\endgroup$ – irchans Mar 21 at 22:21

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.