<s>[INST] 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
 [/INST] 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;

</s>