Building an explicit formula for an algorithm on the compositions of an integer Derive an explicit formula for $a_{n \in \mathbb{Z}^{>0}}$ which is
computed as follows:


*

*List the compositions of $n$.

*Apply the following mapping on the compositions: $1 \longrightarrow 2, \; 2 \longrightarrow 5, \; \text{anything else} \longrightarrow 4$

*Calculate the product of the mapped values.

*Add up the calculated values. This will give $a_n$.


For example, in the case of $n = 3$, the general strategy will play out as follows:
$$3 \longrightarrow 4 = 4$$
$$1 + 2 \longrightarrow 2 \times 5 = 10$$
$$2 + 1 \longrightarrow 5 \times 2 = 10$$
$$1 + 1 + 1\longrightarrow 2 \times 2 \times 2 = 8$$
$$4 + 10 + 10 + 8 = 32$$
Hence, $a_3 = 32$.
I developed the above strategy when working on the following problem:

In how many ways can one pack a  $2 \times 2 \times n$ box with $1
\times 1 \times 2$ bricks?

Conducting research, I found this paper cite the following general formula:
$$a_n = \frac{1}{3}(-1)^n + \frac{1}{6}(2 + \sqrt{3})^{n+1} + \frac{1}{6}(2 - \sqrt{3})^{n+1} \tag{1}$$
They formulate recursive relationships from which the general formula can be formed, which is a different approach from the one I employed. Their work inclines me to believe that my method can be recursively defined, which can then yield a general formula. But I'm unable to formulate a recursive relationship at the moment.
Comments:

*

*I am not looking for alternate ways to solve the original problem (that is the question of tiling bricks) but rather a continuation of my work (that is the general strategy I have described above) to get $(1)$.

*Please approach this problem as if the general formula is not known to you, that is to say, inductive proofs are not viable unless they can be reasonably conjectured.

 A: Your rules correspond to generating function where numbers composed into $k$ elements are given by $(2x+5x^2+4x^3+4x^4+\dots)^k$, so the generating function for your sequence is
$$
f(x)=\sum_{k=1}^{\infty}(2x+5x^2+4x^3+4x^4+\dots)^k.
$$
Simplifying the inner terms using geometric series we can write
$$
f(x)=\sum_{k=1}^{\infty}(\frac{2x+3x^2-x^3}{1-x})^k.
$$
This itself is infinite geometric series and so we can simplify $f(x)$ to
$$
f(x)=\frac{x(2+3x-x^2)}{x^3 - 3x^2 - 3x + 1}.
$$
From this you can get either recurrence or closed form formula by standard tools. For example, by partial fractions decomposition
$$
f(x)=-1+\frac{1}{3}\frac{1}{1+x}+\frac{1}{6}\frac{1}{2-\sqrt{3}-x}+\frac{1}{6}\frac{1}{2+\sqrt{3}-x}.
$$
Each term can be turned into a geometric series on its own, so writting it as such and extracting the coefficient of $x^n$ for $n>0$, you get
$$
\frac{1}{3}(-1)^n+\frac{1}{6}\frac{1}{(2-\sqrt{3})^{n+1}}+\frac{1}{6}\frac{1}{(2+\sqrt{3})^{n+1}}.
$$
Rationalizing the expression using $(2-\sqrt{3})(2+\sqrt{3})=1$ you then get your formula.
