Fountains of Coins and Fibonacci Numbers

Question

I recently came across a problem in Herbert Wilf's Generatingfunctionology book that I can't come up with an elegant solution to and can't find any solutions online. The problem statement begins on page 38

https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf

and concerns 'fountains of coins', basically what you get when you stack rows of coins in 2 dimensions. The book goes through a proof that the generating function for the number of block fountains, basically fountains with no gaps, that can be with a base that is exactly $k$ coins wide. The generating function ends up being

$$F(x) = \frac{1-2x}{1-3x+x^2}$$

It turns out that if you look at the terms in the sequence, they are the odd terms of the Fibonacci numbers, $F_{2N-1}$. The book states this and leaves it as an exercise, but I can't seem to make any progress on any sort of nice combinatorial argument to show this. If anyone has any insight, it would be greatly appreciated!

Answer 1

Use the fact that $F_{2n+1}=F_{2n-1}+\sum_{k=1}^nF_{2k-1}=2F_{2n-1}+\sum_{k=1}^{n-1}F_{2k-1}$, and prove it by induction on $n$. Let $f(n)$ be the number of block fountains with a base of $n$ coins, and assume that $f(k)=F_{2k-1}$ for $k\le n$. Now start with a base of $n+1$ coins. If the second row has no coin in the first available slot, you have essentially a block fountain on a base of the last $n$ coins; there are $f(n)$ of these. If the second row has a coin in the first available slot, the block fountain consisting of all rows but the first has a base of $k$ coins for some $k\in[n]$, and the position of that base relative to the bottom row of the whole fountain is fixed. Thus, this case adds another $\sum_{k=1}^nf(k)=\sum_{k=1}^nF_{2k-1}$ block fountains, for a total of $f(n+1)=F_{2n-1}+\sum_{k=1}^nF_{2k-1}=F_{2n+1}$ block fountains with base $n+1$.

Added: One can also show combinatorially that $f(n+1)=3f(n)-f(n-1)$. As above, start with a base of $n+1$ coins. Also as above, there are $f(n)$ block fountains that have $n$ coins in the second row and $f(n)$ that do not have a coin in the first slot of the second row. Similarly, there are $f(n)$ that do not have a coin in the last slot of the second row. Finally, this counts twice the $f(n-1)$ block fountains that do not have a coin in either of the end slots of the second row, so we get $f(n+1)=3f(n)-f(n-1)$. Then observe that the Fibonacci numbers with odd indices satisfy the same recurrence with the same initial conditions.

Answer 2

$\def\zz{\mathbb{Z}}$Let $G_n = F_{2n+1}$ for all $n \in \zz$.

$F_{2n+1} = F_{2n} + F_{2n-1} = 2 F_{2n-1} + F_{2n-2} = 3 F_{2n-1} - F_{2n-3}$.

Thus $(R^2-3R+1)(G) = 0$ where $R$ is the right-shift operator.

If you want the generating function for just the positive index part of the sequence, you get extra leftovers due to the initial conditions.

Answer 3

Let us call : $Fib(x)$ the generating function associated to the Fibonacci number $(F_k)$. We know that :

$$Fib(x)=\frac{x}{1-x-x^2} $$

Now if we want to make appear something like a serie with only the $F_{2k+1}$ it seems like a good idea to compute :

$$Fib(x)-Fib(-x)=2\sum_{k=0}^{\infty}F_{2k+1}x^{2k+1} $$

$$Fib(x)-Fib(-x)=2x\sum_{k=0}^{\infty}F_{2k+1}(x^2)^k $$

Hence, we see that if $G(y)$ is the generating function for the $(F_{2k+1})$ we must have that :

$$G(x^2)=\frac{Fib(x)-Fib(-x)}{2x} $$

Now it suffices to compute :

$$Fib(x)+Fib(-x)=\frac{x}{1-x-x^2}+\frac{x}{1+x-x^2} $$

$$Fib(x)+Fib(-x)=\frac{2x-2x^3}{1-3x^2+x^4}$$

Hence we have that :

$$G(x^2)=\frac{1-x^2}{1-3x^2+x^4} $$

Hence :

$$G(y)=\frac{1-y}{1-3y+y^2} $$

Now the generating function for the $F_{2k-1}$ is exactly $yG(y)$ hence :

$$\sum_{k\geq 0}F_{2k-1}y^k=\frac{y-y^2}{1-3y+y^2} $$

On the other hand compute :

$$F(y)-1=\frac{1-2y}{1-3y+y^2}-1=\frac{y-y^2}{1-3y+y^2} $$

Then you see that $F(y)-1=yG(y)$ this is exactly saying that the $k$-coefficient of $F(y)$ for $k\geq 1$ is $F_{2k-1}$.