Edit: I added smoothness, hoping to simplify the problem with this additional assumption.


Let me motivate this question first: In signal analysis it is often of interest to understand when a certain function has a fast decaying representation with respect to some basis. I encountered an example where I expected such a fast decaying representation but was unable to show it myself: 


The situation is that one is given a sequence of functions whose supports are only overlapping with their nearest neighbors. Intuitively, I expected that if I would write any of those function in terms of the Gram-Schmidt orthonormalized sequence of all functions, then the expansion coefficients should decay fast. 


Let me now make this more precise:


Take a family of intervals $I\_{2i}:=(i,i+1)$ and $I\_{2i+1}=(\frac{1}{2}+i,\frac{1}{2}+i+1)$ with $i \ge 0$
Those intervals are almost disjoint in the sense that $I\_i \cap I\_j=\emptyset$ if and only if $\left\lvert i-j \right\rvert >1,$ so we only have a nearest neighbor overlap.


We consider a family of smooth functions $h\_i:I\_i \rightarrow \mathbb{R}$ that are $L^2$ normalized (but not orthogonal) where $h\_{i+1}$ is just a translate of $h\_i$ by $\frac{1}{2}$ to the right.


We assume that $\langle h\_0,h\_1 \rangle \neq 0$ and $\langle h\_1,h\_2 \rangle \neq 0$ to avoid trivialities. Due to the condition on the domain, all other $h\_i$ however (besides $h\_0$, $h\_1,$ and $h\_2$) have zero overlap with $h\_1$.


We now consider the Gram-Schmidt orthonormalized sequence $(g\_i)$ of the $h\_i$, i.e. $g\_0:=h\_0$ and $g\_1:=\frac{h\_1-\langle h\_1,g\_0\rangle g\_0}{\left\lVert h\_1-\langle h\_1,g\_0\rangle g\_0 \right\rVert}$ and so on. Note that also $g\_2,g\_3,...$ and so on may now have non-vanishing overlap with $h\_1$, although this one should intuitively still be small.


Clearly, $h\_1=\sum\_{n=0}^{\infty} a\_n g\_n$ for some $a\_n$. 


I would like to know: How rapidly do the coefficients $a\_n$ decay? In particular, is it true that (the following notation means up to a constant) $\left\lvert a\_n \right\rvert \lesssim L^n$ for some $L\in (0,1)$?



Orthonormal basis and decay
Think in the opposite direction: start with an orthonormal sequence $g\_n$ and try to find appropriate $h\_n$. The conditions on $h\_n$ are: $h\_n$ is a linear combination of $g\_0, g\_1, \ldots, g\_n$, $\|h\_n\| = 1$, $\langle h\_n, h\_{n-1}\rangle = \alpha\_n$ for a given $\alpha\_n$ (in your question $\alpha\_n$ is in fact constant), and $\langle h\_n, h\_j \rangle = 0$ for $j \leqslant n - 2$.


Clearly, $h\_0, h\_1, \ldots, h\_n$ span the same subspace as $g\_0, g\_1, \ldots, g\_n$, for we assume that $|\alpha\_n| < 1$ (in fact if $\alpha\_n$ is constant, then necessarily $|\alpha\_n| \leqslant 1/2$). Since $h\_n$ is orthogonal to $h\_0, h\_1, \ldots, h\_{n-2}$, it follows that $h\_n$ is orthogonal to $g\_0, g\_1, \ldots, g\_{n-2}$. Therefore, $h\_n$ is a linear combination of $g\_n$ and $g\_{n-1}$.


This already answers your question: the decay is super-fast, all but two coefficients are zero! However you might be interested in a different thing: what is the coefficient at, say, $h\_0$ in the expansion of $g\_n$ in terms of $h\_0, h\_1, \ldots, h\_n$. This is a much more interesting problem.


Write $h\_n = \beta\_n g\_{n - 1} + \sqrt{1 - |\beta\_n|^2} g\_n$. (We could arbitrarily change the sign of the coefficient at $g\_n$, but the above choice corresponds to the Gram–Schmidt process). Then it is easy to see that $\beta\_0 = 0$ and $$\beta\_n = \alpha\_n \sqrt{1 - |\beta\_{n-1}|^2} .$$ If $\alpha\_n$ is a constant, say $\alpha$, this leads to $$\beta\_n = \alpha \sqrt{\frac{i}{x} \, \frac{F\_{n-1}(i/\alpha)}{F\_n(i/\alpha)}},$$ where $F\_n$ is the Fibonacci polynomial. (To be honest, I found that empirically, but writing up a recurrence equation for $F\_n$ using the one for $\beta\_n$ seems straightforward).


Now write the matrix $B$ of coefficients of the expansion of $h\_n$ in terms of $g\_n$; that is, $B\_{n,n-1} = \beta\_n$, $B\_{n,n} = \sqrt{1 - |\beta\_n|^2}$ and $B\_{n,m} = 0$ if $m \geqslant n + 1$ or $m \leqslant n - 2$. In order to express $g\_n$ as a linear combination of $h\_0, h\_1, \ldots, h\_n$, one needs to invert this matrix.


In the "naively worst case scenario" $\alpha\_n \equiv 1/2$ or $\alpha\_n \equiv -1/2$, one can find $\beta\_n$ and the first column of $B^{-1}$ explicitly: $B^{-1}\_{0,n} = \pm((n + 1)(n + 2)/2)^{-1/2} = O(n^{-1})$. It should be possible to prove that this is indeed the worst case, but I did not attempt to do that.


