You are making a string and have access to pieces of two different lengths, of length 1 inch and of length 2 inch.
The 1 inch pieces come in 5 different fabrics and the 2 inch pieces come in 4 different fabrics.
Find a recurrence relation for the number of ways, $a_n$, to construct a $n$-inch long string.
I am thinking that if you have a $n-1$-inch long string then for the last piece you can choose only among the 1 inch pieces and you have 5 different fabrics of these, and therefore the first part of the recurrence relation would be $a_n = 5a_{n-1}$. Now if you have a $n-2$-inch long string then you can choose the 1 inch pieces in $5^2$ ways and you can choose 2 inch pieces in 4 ways.
So you have $5^2 + 4 = 29$ possibilities.
and
$a_n = 5a_{n-1} + 29a_{n-2}$
with initial conditions $a_0 = 0$ and $a_1 = 5$.
Is there any flaws in my logic here?
The $n$-inch long string can be end with either 1 inch or 2 inches. If it's 1 inch, then the number of such constructions is equal to $5 a_{n-1}$. If it ends with a 2-inch piece, then the number of such constructions is $4 a_{n-2}$.
So the total number of constructions is $5a_{n-1} + 4a_{n-2}$.
In your solution, you double-counted the number of constructions for $n$-inch strings ending with a 1-inch piece. The $5a_{n-1}$ you calculated already includes the $5^2a_{n-2}$.