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.
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.