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
 A: 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.
A: 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;

A: 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.
