Ordered partitions of an integer (with a twist)

Question

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.

Answer 1

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}$$

Answer 2

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}$.

Answer 3

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.