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

-
In the first example, is the replacing of the last element of the partition by 1 really necessary? It seems to work without that as well. – Raskolnikov Jan 7 '12 at 21:39
like this question :) – NikBels Jan 7 '12 at 21:57

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.

-
Brian: Any hints as to how this thing is connected with partition theory? thanks in advance. – NikBels Jan 7 '12 at 21:59
@Nikhil: Not a clue, I’m afraid: I’ve never seen anything like it before. – Brian M. Scott Jan 7 '12 at 22:01
Very interesting nonetheless. – NikBels Jan 7 '12 at 22:03
@NikhilBellarykar: I don't know if it has any connections or consequences, but for me it looks like mastership of OP's teacher in constructing tasks for students rather than some deep properties of partitions. If particular objects can be constructed recursively then it is quite probable that one can somehow associate Fibonacci numbers with them. Even in two ways here:) – savick01 Jan 8 '12 at 13:15
@savick01: well, I beg to differ. I do think that we are looking at something pretty interesting here. I am not qualified enough to comment about any deep properties of either partitions or fibonacci numbers, but, to me, this kind of thing looks like a bolt from the blue, hence my question. Brian's proof is correct but it doesn't tell us something about what is it about partitions that makes this thing possible.. Who knows, maybe there is something really simple behind all this. But till then, this is a source of mystery and wonder to me. – NikBels Jan 8 '12 at 18:40

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.

-

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;

-