<s>[INST] Ordered partitions of an integer (with a twist) I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has 2 possible colours. For example, 
\begin{align}
2
&=2\\
&={\color\red{1}}+{\color\red{1}}\\
&={\color\green{1}}+{\color\green{1}}\\
&={\color\green{1}}+{\color\red{1}}\\
&={\color\red{1}}+{\color\green{1}}\\
\end{align}
so in this case, $P_1(2,2)=5$.
This is my (failed) attempt to derive a formula for $P_1(k,n)$. Consider a case where the number $n$ is expressed as a sum of $m$ natural numbers, out of which there are $j$ number of $1$s. The number of possible ways to do so is given by
$$\binom{m}{j}[x^n]x^j(x^2+x^3+...)^{m-j}$$
Now we look at how many partitions we can get from this particular case. Since there are $j$ number of $1$s, we would have to multiply by $k^j$, and since $0\le j \le m$ and $1 \le m \le n$ we have
\begin{align}
P_1(k,n)
&=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}[x^n]x^j(x^2+x^3+...)^{m-j}\\
&=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}[x^{n-2m+j}](1-x)^{-(m-j)}\\
&=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{m-j+n-2m+j-1}{n-2m+j}\\
&=\sum^{n}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\
&=2^{n-1}+\sum^{n-1}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\
\end{align}
I have tried using the "snake-oil" method to compute this sum, that is,
$$P_1(2,n)=2^{n-1}+[x^{n-1}]\sum_{n\ge 1}\sum^{n-1}_{m=1}\sum^{m}_{j=0}k^j\binom{m}{j}\binom{n-m-1}{m-j-1}x^{n-1}$$
but I, embarrassingly, have trouble with changing the order of summation and determining the limits of summation.

This is where I am stuck, and I would like to seek your help in finding a closed form for this sum, and in particular, proving that
\begin{align}
P_1(2,n)
&=2^{n-1}+\sum^{n-1}_{m=1}\sum^{m}_{j=0}2^j\binom{m}{j}\binom{n-m-1}{m-j-1}\\
&=F_{2n+1}
\end{align}
Help will be greatly appreciated. Thank you.
 [/INST] The derivation of the generating function can also done from first principles, without using the recurrence. We have straightforwardly that these partitions have the generating function
$$\sum_{q\ge 0} \left(\frac{z}{1-z} + z\right)^q$$
where we have added in the quantity $z$ to account for the fact that there are two types of one value. The index starts at zero which produces a count of one empty ordered partition. The parameter $q$ counts the number of elements in the ordered partition.
This yields
$$\sum_{q\ge 0} \left(\frac{2z-z^2}{1-z}\right)^q
= \frac{1}{1-(2z-z^2)/(1-z)}
= \frac{1-z}{1-z-2z+z^2}
= \frac{1-z}{1-3z+z^2}.$$
Now the generating function of the Fibonacci numbers is
$$\sum_{k\ge 0} F_k z^k =\frac{z}{1-z-z^2}$$
so that odd Fibonacci numbers are generated by
$$\sum_{k\ge 0} F_{2k+1} z^{2k+1} =
\frac{1}{2} \frac{z}{1-z-z^2}
+ \frac{1}{2} \frac{z}{1+z-z^2}.$$
Therefore 
$$\sum_{k\ge 0} F_{2k+1} z^{2k} =
\frac{1}{2} \frac{1}{1-z-z^2}
+ \frac{1}{2} \frac{1}{1+z-z^2}
= \frac{1}{2} \frac{2-2z^2}{(1-z^2)^2-z^2}.$$
Hence $$\sum_{k\ge 0} F_{2k+1} z^k =
\frac{1-z}{(1-z)^2-z}
= \frac{1-z}{1-3z+z^2}.$$
This proves the claim.
</s>