Does a linear Recurrence relation with an nonlinear relation between elements can be solved by a closed formula?

Question

I came across with this cool recurrence relation, and unfortunately i couldn't find sufficient mathematical tools to form it to a closed formula. i read several posts from math overflow saying that any linear recurrence can be made to a closed formula, but doesn't it depend on the way the 'right wing elements' are chosen? $$a_n = \sum_{\substack{1\le i\le n\\ \text{$i$ a power of 2}\\}}a_{n-i},\qquad a_0=1,\;a_1=1\;a_2=2.$$ For example, the 7'th term of this recurrence relation is $$a_7 = a_6 + a_5 + a_3,$$ but the 16'th item is $$a_{16} = a_{15} + a_{14} + a_{12} + a_8 + a_0.$$

Do these kinds of relations have solutions by a closed formula as well?

Answer 1

Let $$f(z)=\sum_{n=0}^\infty a_nz^n$$ be the generating function of your sequence. Put $$\phi(z)=\sum_{n=0}^\infty b_nz^n=\sum_{n=0}^\infty z^{2^n}=z+z^2+z^4+\ldots,$$ where $b_n=1$ when $n$ is a power of $2$, and $b_n=0$ otherwise. Then the RHS of your recurrency is the $n$-th coefficient of $\phi f$. And recurrency is valid for $n\geq 1$. So $$f-1=\phi f,\quad f=\frac{1}{1-\phi}=\sum_{n=0}^\infty\phi^n.$$ This is a kind of "explicit formula" (for the generating function). The rest depends on what you mean exactly by "explicit expression".

You want $a_n$ to be some function of $n$? What kind of function? Entering $$1,1,2,3,6,10,18,31,...$$ in the Encyclopedia of integer sequences does not give a result.

Function $\phi$ solves the functional equation $\phi(z^2)=1+\phi$ and it is certainly not elementary (every point of the unit circle is a singularity). There is a theorem which says that $\phi$ does not satisfy any algebraic ODE (because of the large gaps).