Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon.

We call an ordered Partition of a positive integer $n$ as the way of writing $n$ as a sum of one or more positive integers, where the order of the sum DOES matter. For example, there are $4$ ordered partitions of $3$, namely $1+1+1, 1+2,2+1,3$

Now suppose we replace the last term of each above partition with a $1$, multiply the terms of each individual partition, then add the results all together. In this manner we get: $(1\cdot 1 \cdot 1 )+ (1 \cdot 1 )+ (2 \cdot 1) +(1)$ respectively, which equals $5$, which curiously is a Fibonacci number! Can someone please explain why this result is always a Fibonacci number? (Do some more calculations if you are not yet convinced.)

Now here is a more challenging relationship I found. Given any partition sum, keep only the first, third, fifth,... term. Replace each such term $x$ by $2^{x-1}$ and multiply the results. So as an example, the sum $2+4+1+3+5$ would become $2^12^02^4=32$. Now do this to every ordered partition of $n$ and add the result. Curiously, the sum is always $F_{2n}$. Can someone please explain this as well?

Thank you so much for your time!

Edit: this is problematic since I can't write comments as I am not a user, but yes In the first example replacing a 1 or not will still yield a fibonacci sum-product, but I have already proven the case where you do nt replace with a 1

Solution 1:

The first relationship is actually more interesting than you suggest. Specifically, applying your recipe to the ordered partitions of $n$ produces $F_{2n-1}$, while adding the products without reducing the last entry to $1$ produces $F_{2n}$.

It’s not too hard to see why this works. Suppose that it’s true for some $n$, and consider the ordered partitions of $n+1$. They are of two types: those that end in $1$, and those that don’t. Each partition of $n+1$ that ends in $1$ is obtained from a partition $\pi$ of $n$ by appending $+1$; its reduced product is the product of the entries in $\pi$, so the sum of the reduced products of these partitions of $n+1$ is $F_{2n}$.

Each partition of $n+1$ that does not end in $1$ is obtained from a partition $\pi$ of $n$ by adding $1$ to its last element; its reduced product is the same as the reduced product of $\pi$, so the sum of the reduced products of these partitions of $n+1$ is $F_{2n-1}$. Thus, the sum of the reduced products of all of the ordered partitions of $n+1$ is $F_{2n}+F_{2n-1}=F_{2n+1}=F_{2(n+1)-1}$, as desired.

The sum of the unreduced products of the partitions of $n+1$ that end in $1$ is the same as the sum of their reduced products, or $F_{2n}$, so to complete the argument, we need only show that the sum of the unreduced products of the partitions that do not end in $1$ is $F_{2n+1}$. But this is clear: if $\pi'$ is an ordered partition of $n+1$ obtained by adding $1$ to the last element of some ordered partition $\pi$ of $n$, the unreduced product of $\pi'$ is the sum of the reduced and unreduced products of $\pi$. Summing over all such partitions of $n+1$ then yields a total of $F_{2n}+F_{2n-1}=$ $F_{2n+1}$, just as in the last paragraph.

Of course the induction gets off the ground with no difficulty, since the sums for $n=1$ are $F_1=1=F_2$.

I’d meant to add this a while back, but I got busy and forgot:

This differs from savicko1’s argument chiefly in that it looks only at the immediately preceding integer.

The second question can be dealt with similarly. Let $P(n)$ be the set of ordered partitions of $n$. Call an ordered partition of $n$ odd or even according as the number of terms is odd or even. Let $P_o(n)$ be the set of odd ordered partitions of $n$, $P_o^-$ the set of odd ordered partitions of $n$ whose last term is $1$, and $P_o^+(n)$ be the set of odd ordered partitions of $n$ whose last term is greater than $1$, and define $P_e(n)$, $P_e^-(n)$, and $P_e^+(n)$ similarly for even ordered partitions of $n$. For each ordered partition $\pi$ of $n$ let $f(\pi)$ be the product of the factors $2^{x-1}$ as $x$ ranges over the odd-numbered terms of $\pi$. Finally, let $$s(n)=\sum_{\pi\in P(n)}f(\pi)\text{ and }t(n)=\sum_{\pi\in P_o(n)}f(\pi)\;.$$

Then $$\begin{align*} &\sum_{\pi\in P_o^-(n+1)}f(\pi)=\sum_{\pi\in P_e(n)}f(\pi)=s(n)-t(n)\;,\\ &\sum_{\pi\in P_o^+(n+1)}f(\pi)=2\sum_{\pi\in P_o(n)}f(\pi)=2t(n)\;,\\ &\sum_{\pi\in P_e^-(n+1)}f(\pi)=\sum_{\pi\in P_o(n)}f(\pi)=t(n)\;,\text{ and}\\ &\sum_{\pi\in P_e^+(n+1)}f(\pi)=\sum_{\pi\in P_e(n)}f(\pi)=s(n)-t(n)\;, \end{align*}\tag{1}$$

and since the lefthand sides of $(1)$ sum to $s(n+1)$, $$ s(n+1)=2s(n)+t(n)\tag{2}$$ and $$t(n+1)=\sum_{\pi\in P_o^-(n+1)}f(\pi)+\sum_{\pi\in P_o^+(n+1)}f(\pi)=s(n)+t(n)\;.$$ If $s(k)=F_{2k}$ for $k\le n$, then $$\begin{align*} s(n+1)&=2F_{2n}+t(n)\\ &=2F_{2n}+s(n-1)+t(n-1)\\ &=2F_{2n}+s(n-1)+\big(s(n)-2s(n-1)\big)\qquad\text{(from }(2)\text{)}\\ &=3F_{2n}-F_{2n-2}\\ &=2F_{2n}+F_{2n-1}\\ &=F_{2n}+F_{2n+1}\\ &=F_{2n+2}\;, \end{align*}$$

and the result follows by induction.

Solution 2:

The second part of the question

Let's denote a sum of products ($\prod 2^{x_{2k+1}-1}$) defined in the second problem for a set of partitions $\Pi$ by $S(\Pi)$.

Every partition $\pi$ consists of either even or odd number of summands. I will call it an even or odd partition respectively. Now: every even partition $\pi$ of $n>0$ is a partition of some $m<n$ with one additional summand: $n-m$. There is even a bijection between partitions of $n$ and partitions of $m<n$ if we assume that there is one empty partition of $m=0$.

Now, a key observation: the set $E_n$ of even partitions of $n$ derive from odd partitions of $m$ and symmetrically for the set $O_n$ of odd partitions. What is more, a number $S(O_n)$ is equal to $F_{2n-1}$ and the number $S(E_n)$ is $F_{2n-2}$. By adding those two we get the thesis.

But we have to prove those equalities. It will be a "parallel" inductive proof - from thesis for $O_m\ \& \ E_m$ we will get the thesis for $O_n\ \& \ E_n$. First $S(E_n)$. $$S(E_n) = S(O_{n-1}) + S(O_{n-2}) + \ldots + S(O_{1}) = $$ $$= F_{2n-3} + F_{2n-5} + \ldots + F_1 = (F_0=0) = F_{2n-2}.$$

With $S(O_n)$ it is a little bit harder. $$S(O_n) = S(E_{n-1})\cdot 2^{1-1} + S(E_{n-2})\cdot 2^{2-1} + \ldots S(E_{2})\cdot 2^{(n-2)-1} + 2^{n-1} = $$ (note that $E_1$ is empty) $$= F_{2n-4} + F_{2n-6}\cdot 2 + \ldots + F_2\cdot 2^{(n-2)-1} + 2^{n-1} = $$ $$= F_{2n-4} + 2 (F_{2n-6} + \ldots + F_2\cdot 2^{(n-3)-1} + 2^{(n-1)-1}) = $$ $$ = F_{2n-4} + 2 S(O_{n-1}) = F_{2n-4} + 2F_{2n-3} = F_{2n-2} + F_{2n-3} = F_{2n-1} \ \square$$

Remark about the first part of the question

The same trick can be done in the case of the first question, where we compute a different sum $\hat{S}(\Pi)$ from a set of partitions $\Pi$. In that case one doesn't have to split the set $\Pi_n$ of partitions of $n$ into $E_n$ and $O_n$ and instead of $S(E_{n-x})2^{x-1}$ they simply get $\tilde{S}(\Pi_{n-x})\cdot 1$ (and $1$ instead of $2^{n-1}$). Note that one constructs a "reduced" sum $\hat{S}$ by adding "unreduced" sums $\tilde{S}$. Since there is a highly assessed answer above and it is not so hard to formalise this approach when the sketch is provided and finally it is a homework, I skip the details.

Solution 3:

This problem has a solution using ordinary generating functions.

First question. Observe that $$\sum_{q\ge 0} q z^q = \frac{z}{(1-z)^2}.$$

Therefore the generating function of the contribution from partitions with $k$ terms is given by $$\left(\frac{z}{(1-z)^2}\right)^{k-1} \frac{z}{1-z}$$ and the contribution from all partitions is $$p(z) = \sum_{k\ge 1} \left(\frac{z}{(1-z)^2}\right)^{k-1} \frac{z}{1-z} = \frac{z}{1-z} \frac{1}{1-z/(1-z)^2} \\= \frac{z}{1-z} \frac{(1-z)^2}{(1-z)^2-z} = \frac{z(1-z)}{1 - 3z + z^2}.$$ Recall that the generating function of the Fibonacci numbers is $$\sum_{q\ge 0} F_q z^q = \frac{z}{1-z-z^2}.$$ It follows that $$\sum_{q\ge 0} F_{2q+1} z^{2q+1} = \frac{1}{2}\frac{z}{1-z-z^2} + \frac{1}{2}\frac{z}{1+z-z^2} \\= z \frac{1-z^2}{(z^2+z-1)(z^2-z-1)} = z \frac{1-z^2}{(z^2-1)^2-z^2}$$ so that $$\sum_{q\ge 0} F_{2q+1} z^{q+1} = z \frac{1-z}{1-3z+z^2}$$ which finally yields $$[z^n] p(z) = F_{2n-1}.$$

Second question.

To start observe that $$\frac{1}{2} \sum_{q\ge 1} 2^q z^q = \frac{z}{1-2z}.$$

Here the generating function is for $k=2q$ even ($k$ -- number of elements in the partition) $$\left(\frac{z}{1-2z}\right)^q \left(\frac{z}{1-z}\right)^q$$ and for $k=2q+1$ odd $$\left(\frac{z}{1-2z}\right)^{q+1} \left(\frac{z}{1-z}\right)^q.$$ Collecting both contributions we obtain $$q(z) = \sum_{q\ge 1} \left(\frac{z}{1-2z}\right)^q \left(\frac{z}{1-z}\right)^q + \sum_{q\ge 0} \left(\frac{z}{1-2z}\right)^{q+1} \left(\frac{z}{1-z}\right)^q.$$ Simplify this to get $$\frac{z^2/(1-2z)/(1-z)}{1-z^2/(1-2z)/(1-z)} + \frac{z}{1-2z} \frac{1}{1-z^2/(1-2z)/(1-z)}$$ or $$\frac{z^2}{(1-2z)(1-z)-z^2} + \frac{z(1-z)}{(1-2z)(1-z)-z^2}$$ which is $$\frac{z}{(1-2z)(1-z)-z^2} = \frac{z}{1-3z+z^2}.$$ Recall the generating function of the Fibonacci numbers to get $$\sum_{q\ge 0} F_{2q} z^{2q} = \frac{1}{2}\frac{z}{1-z-z^2} - \frac{1}{2}\frac{z}{1+z-z^2} = \frac{z^2}{(1-z^2)^2-z^2}$$ so that $$\sum_{q\ge 0} F_{2q} z^q = \frac{z}{(1-z)^2-z} = \frac{z}{1-3z+z^2}.$$ This finally yields $$[z^n] q(z) = F_{2n}.$$

Addendum. The following Maple code can be used to verify the above results and further investigate these numbers. Maple has a Fibonacci routine with the name fibonacci.

with(combinat);

q := proc(n)
option remember;
local s, p, q, x, k;
    s := 0;

    for p in partition(n) do
        for q in permute(p) do
            x := [seq(q[k], k = 1 .. nops(q) - 1), 1];
            s := s + mul(x[k], k = 1 .. nops(x))
        od;
    od;
    s
end;


q2 := proc(n)
option remember;
local s, p, q, x, k;
    s := 0;

    for p in partition(n) do
        for q in permute(p) do
            x := [seq(q[2*k+1], k=0..iquo(nops(q)-1, 2))];
            s := s + mul(2^(x[k]-1), k = 1 .. nops(x))
        od;
    od;
    s
end;