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?

Hardy & Wright. $\endgroup$