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.
 A: Observation 1: For positive integer $k$,  $F_{2k}=F_{2k-1}+F_{2k-2}=F_{2k-1}+F_{2k-3}+F_{2k-4}=\dots=F_{2k-1}+F_{2k-3}+\dots+F_1$.  (There would be an $F_0$ term at the end, but $F_0=0$.)
Your identity can now be established recursively. For ordered partitions of $n$, we look at cases according to the first term of a partition.  If the first term is $1$, we have two ways (colors) to choose that $1$, and then we have $P(2,2n-1)$ to arrange the remaining terms.  This gives $2\cdot P(2,n-1)$ ordered partitions of $n$ starting with $1$.  If the first term is $2$, then there are $P(2,n-2)$ ways to complete the partition.  And so on.  Hence $P(n)=2P(2,n-1)+P(2,n-2)+\cdots+ P(2,1)$. If we assume inductively that $P(2,k)=F_{2k+1}$, then we obtain
$$\begin{array}{ccl}
P(2,n)&=&2F_{2n-1}+F_{2n-3}+F_{2n-5}+\cdots+F_{1}\\&=&F_{2n-1}+(F_{2n-1}+F_{2n-3}+F_{2n-5}+\cdots+F_{1})\\&=&F_{2n-1}+F_{2n} \hspace{1in}\\&=&F_{2n+1} \end{array}$$
A: Thanks to @paw88789's insightful explanation, I was able to derive a closed form for $P_1(2,n)$ without using any prior knowledge of the answer. The recurrence relation is
\begin{align}
a_n
&=2a_{n-1}+a_{n-2}+...+a_1+1\\
&=1+a_{n-1}+\sum^{n-1}_{m=1}a_m
\end{align}
Applying the forward difference operator $\Delta_n$ to both sides yields
\begin{align}
a_{n+1}-a_n&=a_n-a_{n-1}+a_n\\
a_{n+2}&=3a_{n+1}-a_n
\end{align}
Define the generating function
$$A(x)=\sum_{n\ge 1}a_nx^n$$
In terms of $A(x)$, the recurrence relation is
$$\frac{A(x)-2x-5x^2}{x^2}=\frac{3A(x)-6x}{x}-A(x)$$
Solving for $A(x)$ gives
\begin{align}
A(x)
&=\frac{2x-x^2}{1-3x+x^2}\\
&=\frac{1-x}{1-3x+x^2}-1\\
\end{align}
Extract the coefficient
\begin{align}
a_n
&=[x^n]\left(\frac{1-x}{1-3x+x^2}\right)\\
&=\frac{1}{\sqrt{5}}[x^n]\left(\frac{\tau}{x-(\tau+1)}-\frac{\phi}{x-(\phi+1)}\right)\\
&=\frac{1}{\sqrt{5}}\left(\phi\left(\frac{1}{\phi +1}\right)^{n+1}-\tau\left(\frac{1}{\tau +1}\right)^{n+1}\right)\\
&=\frac{1}{\sqrt{5}}\left(\phi(1+\tau)^{n+1}-\tau(1+\phi)^{n+1}\right)\\
&=\frac{1}{\sqrt{5}}\left(\phi^{2n+1}-\tau^{2n+1}\right)\\
\end{align}
where $\phi=\dfrac{1+\sqrt 5}{2}$ and $\tau=\dfrac{1-\sqrt 5}{2}$.
A: 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.
