Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Question

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for $A_n$, and it is quite simple. I can find it using the formalism of generating functions. But I wonder, is there another way to derive an explicit formula, which is perhaps, more ad hoc? Of course, generating functions are very beautiful and useful, but nevertheless I wonder if there is an alternative way. Imagine you must explain this to a student who doesn't know power series yet.

I do not ask how to verify that the formula (if one knows or guesses it for some reason) satisfies the recurrence - this is an easy exercise with geometric sums. The formula is $A_n = 4 \cdot 6^{n-1}$ for $n \geq 1$. But this is not so important, because my question is rather about the general method.

By the way, $A_n$ is the number of tilings of an $8n \times 3$-rectangle with $L$-tetrominoes. The recurrence relation holds since $2^{k+1}$ is the number of irreducible tilings of an $8k \times 3$-rectangle.

Answer 1

I don't know if consider this method as "more ad hoc" but:

Divide the equality by $2^n$, you get that

$$ \frac{A_n}{2^n} = 2 \sum_{k=1}^n \frac{A_{n-k}}{2^{n-k}}.$$

Then, you define $v_n = \frac{A_n}{2^n}$, it gives you that

$$ v_n = 2\sum_{k=0}^{n-1} v_k, $$ and $$ v_{n-1} = 2\sum_{k=0}^{n-2} v_k. $$

So subtracting these equalities tells you that (for all $n\ge 2$) $$v_n-v_{n-1}=2v_{n-1} \qquad \Leftrightarrow \qquad v_n=3v_{n-1}.$$

It gives you that $\frac{A_n}{2^n}=v_n = 3^{n-1} v_1 = 2\cdot 3^{n-1}$ and consequently $A_n = 4\cdot6^{n-1}.$

Answer 2

The equivalent recurrence $A_n = \sum_{i=0}^{n-1} 2^{n-i+1}A_i$ asks us to find an element of the kernel of the infinite matrix $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & \cdots \\ 2^2 & -1 & 0 & 0 & 0 & \cdots \\ 2^3 & 2^2 & -1 & 0 & 0 & \cdots \\ 2^4 & 2^3 & 2^2 & -1 & 0 & \cdots \\ 2^5 & 2^4 & 2^3 & 2^2 & -1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$$ Seeing this, I suddenly feel the urge of subtracting twice each row from the next --- starting from the bottom --- to obtain the equivalent problem of finding an element of the kernel of the infinite matrix $$\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & \cdots \\ 4 & -1 & 0 & 0 & 0 & \cdots \\ 0 & 6 & -1 & 0 & 0 & \cdots \\ 0 & 0 & 6 & -1 & 0 & \cdots \\ 0 & 0 & 0 & 6 & -1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$$ The general element of the kernel of the latter matrix is evidently $A_n = 4\cdot6^{n-1}\cdot A_0$ for $n \geq 1$.

This reasoning would be totally fine if these were finite matrices, but there is an issue with carrying out infinitely many elementary row operations, especially "starting from the bottom". However, after a step back, it becomes clear that this is just a psychological difficulty: we don't need to "do" this as a sequence of elementary row operations, it is evident to see, row by row, that any element of the kernel of the first matrix is also an element of the kernel of the second matrix and vice versa.