This problem has come up in a puzzle I've been trying to solve --
Given a 1xn board and tiles up to 1xn length how many ways can you construct the board. All of the tiles are the same color, let's call it grey, except for the 1x1 title which has two possible colors, red and green. How many possible distinct tilings are possible (counting both distinct coloring and tile combinations).
From a different approach to the same puzzle I've found the answer to satisfy the recurrence relation $x(n) = 2x(n-1) + \sum_{i=0}^{n-2}x(i)$ where $x(0)=0$, $x(1)=1$, which can be shown to be the fibonacci sequence of odd parity $f(2n-3)$. But I'm struggling to show why this is recurrence is true from a combinations approach.
After some research I've been unable to find a similar problem and this one becomes quite difficult when I try to dive into it. So if someone could point me to a source, suggest a solution, or point out something obvious I'm missing it would be greatly appreciated.
Every tiling of the $1\times n$ board starts with some valid tile. There are two valid $1\times1$ tiles, and then the rest of the tiling tiles a $1\times(n-1)$ board—that gives the $2x_{n-1}$ term. Otherwise, for each $2\le j\le n$, there is one valid $1\times j$ tile, and then the rest of the tiling tiles a $1\times(n-j)$ board—that gives the term $\sum_{j=2}^n x_{n-j} = \sum_{i=0}^{n-2} x_i$. By the way, it feels like the initial condition should be $x_0=1$ rather than $x_0=0$ (there is one tiling of the empty board, namely the empty tiling), and thus $x_1=2$ rather than $x_1=1$.