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.

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.
