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

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?

• Why the down vote? This seems interesting and non-trivial. My guess is that the answer is no. In any case, when people say that "every linear recurrence can be made to a closed formula," they mean linear recurrences in which the number of previous terms that appear in the recurrence is bounded. In other words, they have the form $a_n=L(a_{n-1},\ldots,a_{n-k})$ for a fixed linear form $L$, so in particular $k$ can't change. Nov 17, 2017 at 12:05
• The question title is misleading - your relations are linear, just not linear of bounded order. The answer to your question is that some of these problems will have closed form solutions and some will not. And if you work on this, you will need to decide precisely what you mean by a `closed formula” Nov 17, 2017 at 13:40
• At least, the partition function satisfies some recurrence relation of a similar form. See Formula (19.10.2) of Hardy & Wright. Nov 17, 2017 at 15:00

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).
• @DsCpp I think your definition of ‘closed formula’, though appealing, is a bit misleading. Can you compute $\sin(x)$ in $O(1)$ time?