show/hide this revision's text 4 added 6 characters in body

Let me slightly change the notation. You have some sequence $\mathbf{a}=a_0,a_1,\cdots$ with each $a_i$ either $0$ or $1$. Define a sequence $u_0,u_1,u_2,\cdots$ by setting $u_m=0$ for $m \lt 0$, $u_0=1$ and for any $n \ge 0$, $u_{n+1}=\sum_{i=1}^{\infty}a_iu_{n-i}.$ As you note in a comment, if $a_1=1$ then $u_i$ is a non-decreasing and eventually increasing sequence (excluding a trivial case). The sequence $u_i$ will eventually be increasing as long as the set of $j$ with $a_j=1$ has a $\gcd$ of $1$.

Consider the power series $f(r)=r-(a_0+\frac{a_1}{r}+\frac{a_2}{r^2}+\cdots).$ Then $f(r)$ is defined and increasing for $r \gt 1.$ There is a unique $\lambda=\lambda_{\mathbf{a}}>1$ with $f(\lambda)=0.$ I think that there should be a constant $c \le 1$ with $\lim \frac{a_n}{c\lambda^n}=1$. We can also say that $\lambda \le 2$ with equality only in the degenerate case that $a_i=1$ for all $i$. For any $1 \lt r \lt 2$ we can create an $\mathbf{a}$ with $\lambda_{\mathbf{a}}=r$ by simply choosing the $a_i$ one at a time to keep the (non-decreasing) partial sums of $f(r)$ non-negative.

We can partially order the possible sequences $\mathbf{a}=(a_i)$ by saying $\mathbf{a}<mathbf{b}$<\mathbf{b}$ when $a_i=b_i$ for $0 \le i \lt j$ and $0=a_j<b_j=1.$ In this case, $\lambda{\mathbf{a}}<\lambda_{\mathbf{b}}$.

In case $a_i=0$ from some point on we know how to find $\lambda$ as the root of a polynomial and if $a_i=1$ from some point on we again know how to find $\lambda$ as the root of a polynomial (perhaps with a coefficient equal to $2$.So this gives us both a lower bound and an upper bound on $\lambda_{\mathbf{a}}$ based on any initial portion of $\mathbf{a}.$

I'll stop there for now although probably more can be said.

Consider the $2^d$ sequences $\mathbf{a}$ with $a_{d+m}=a_d$ a_{d+m}=0$ for $m \gt 0.$ If all the roots, real and complex , of $f(r)$ are plotted then you should get a picture something like the one below. This plot is for $d=11$ d=12$ you can see a similar one at this question

alt text .

show/hide this revision's text 3 uploaded a picture

Let me slightly change the notation. You have some sequence $\mathbf{a}=a_0,a_1,\cdots$ with each $a_i$ either $0$ or $1$. Define a sequence $u_0,u_1,u_2,\cdots$ by setting $u_m=0$ for $m \lt 0$, $u_0=1$ and for any $n \ge 0$, $u_{n+1}=\sum_{i=1}^{\infty}a_iu_{n-i}.$ As you note in a comment, if $a_1=1$ then $u_i$ is a non-decreasing and eventually increasing sequence (excluding a trivial case). The sequence $u_i$ will eventually be increasing as long as the set of $j$ with $a_j=1$ has a $\gcd$ of $1$.

Consider the power series $f(r)=r-(a_0+\frac{a_1}{r}+\frac{a_2}{r^2}+\cdots).$ Then $f(r)$ is defined and increasing for $r \gt 1.$ There is a unique $\lambda=\lambda_{\mathbf{a}}>1$ with $f(\lambda)=0.$ I think that there should be a constant $c \le 1$ with $\lim \frac{a_n}{c\lambda^n}=1$. We can also say that $\lambda \le 2$ with equality only in the degenerate case that $a_i=1$ for all $i$. For any $1 \lt r \lt 2$ we can create an $\mathbf{a}$ with $\lambda_{\mathbf{a}}=r$ by simply choosing the $a_i$ one at a time to keep the (non-decreasing) partial sums of $f(r)$ non-negative.

We can partially order the possible sequences $\mathbf{a}=(a_i)$ by saying $\mathbf{a}<mathbf{b}$ when $a_i=b_i$ for $0 \le i \lt j$ and $0=a_j

In case $a_i=0$ from some point on we know how to find $\lambda$ as the root of a polynomial and if $a_i=1$ from some point on we again know how to find $\lambda$ as the root of a polynomial (perhaps with a coefficient equal to $2$.So this gives us both a lower bound and an upper bound on $\lambda_{\mathbf{a}}$ based on any initial portion of $\mathbf{a}.$

I'll stop there for now although probably more can be said.

Consider the $2^d$ sequences $\mathbf{a}$ with $a_{d+m}=a_d$ for $m \gt 0.$ If all the roots, real and complex , of $f(r)$ are plotted then you should get a picture something like the one below. This one comes form polynomials with all coefficients $\pm 1$ . The illustration plot is lifted from this question alt text . For the problem here I would expect more of a C shape around the unit circle with distance from th origin between $\sqrt{2}$ and for $1/\sqrt{2}$. There should also be d=11$ you can see a portion of the real line between 1 and 2 along with another portion centered near $-1$ on the negative real axissimilar one at this question

alt text .

show/hide this revision's text 2 rewrite

I like

Let me slightly change the question, but it needs to be modifiednotation. In the positive direction we can bound You have some sequence $\lambda$ in whatever correct result is true as \mathbf{a}=a_0,a_1,\cdots$ with each $u_n a_i$ either $0$ or $1$. Define a sequence $u_0,u_1,u_2,\cdots$ by setting $u_m=0$ for $m \lt 2^n$ 0$, $u_0=1$ and for any $n \gt 1.$ In the negative directionge 0$, it is easy to arrange for $u_1=u_3=u_5=\cdots=0$ u_{n+1}=\sum_{i=1}^{\infty}a_iu_{n-i}.$ As you note in a comment, just set if $a_{2k+1}=0$ for all a_1=1$ then $k$ u_i$ is a non-decreasing and let the even values eventually increasing sequence (excluding a trivial case). The sequence $a_{2k}$ u_i$ will eventually be a mix increasing as long as the set of $0$ and j$ with $a_j=1$ has a $\gcd$ of $1$.To avoid that it might be enough to say that there

Consider the power series $f(r)=r-(a_0+\frac{a_1}{r}+\frac{a_2}{r^2}+\cdots).$ Then $f(r)$ is no arithmetic progression which defined and increasing for $r \gt 1.$ There is all a unique $0.$ Or one might be able to say \lambda=\lambda_{\mathbf{a}}>1$ with $f(\lambda)=0.$ I think that there are should be a finite number of arithmetic progressions each constant $c \le 1$ with its own growth rate.

Can you give a particular example $\lim \frac{a_n}{c\lambda^n}=1$. We can also say that $\lambda \le 2$ with equality only in the kind of bound degenerate case that you would like? $a_i=1$ for all $i$. For a finite recurrence any $1 \lt r \lt 2$ we can create an $\mathbf{a}$ with $\lambda_{\mathbf{a}}=r$ by simply choosing the $a_i$ one has at a growth rate time to keep the (non-decreasing) partial sums of $f(n)\lambda^n$ f(r)$ non-negative.

We can partially order the possible sequences $\mathbf{a}=(a_i)$ by saying $\mathbf{a}<mathbf{b}$ when $a_i=b_i$ for some polynomial $f$ 0 \le i \lt j$ and constant $\lambda.$ I'm not sure, but I expect that one could choose the 0=a_j

In case $a_i$ a_i=0$ from some point on an ad hoc basis we know how to get find $\lambda$ as the root of a growth rate polynomial and if $g(n) \lambda^n$ a_i=1$ from some point on we again know how to find $\lambda$ as the root of a polynomial (perhaps with a coefficient equal to $g(n)$ 2$.So this gives us both a lower bound and an upper bound on $\lambda_{\mathbf{a}}$ based on any initial portion of $\mathbf{a}.$

I'll stop there for now although probably more exotic increasing function such as can be said.

Consider the $n 2^d$ sequences $\mathbf{a}$ with $a_{d+m}=a_d$ for $m \sqrt{n}.$gt 0.$ If all the roots, real and complex , of $f(r)$ are plotted then you should get a picture something like the one below. This one comes form polynomials with all coefficients $\pm 1$ . The illustration is lifted from this question alt text . For the problem here I would expect more of a C shape around the unit circle with distance from th origin between $\sqrt{2}$ and $1/\sqrt{2}$. There should also be a portion of the real line between 1 and 2 along with another portion centered near $-1$ on the negative real axis.
show/hide this revision's text 1