Determine whether $A215928(n)=G_n$.

Question

Let $G_0=1$ and $G_{n+1}=F_0G_n+F_1G_{n-1}+\cdots+F_nG_0$, where $F_n$ is the $n$th term of the Fibonacci sequence, i.e., $F_0=F_1=1$ and $F_{n+1}=F_n+F_{n-1}$.

Let $P_0=P_1=1,\ P_2=2,$ and $P_{n+1}=2P_n+P_{n-1}$ for $n>1$.

Is $P_n=G_n$?

Edit: set $P_2=2$, thanks to Daniel R.

Answer 1

Here is an inductive argument:

The base case obviously holds.

Assume that $P_k=G_k$ for all $k \le n$.

Now we want to prove that $P_{n+1} = G_{n+1}$, i.e. $P_{n+1}-G_{n+1}=0$.

$$\require{cancel} \begin{align}\\ P_{n+1}-G_{n+1} &= 2P_n+P_{n-1}-F_0G_n-F_1G_{n-1}-\dots-F_nG_0\\ &=\{\text{induction hypothesis}\}\\ &=\cancel 2G_n+\cancel{G_{n-1}}-\cancel{F_0G_n}-\cancel{F_1G_{n-1}}-F_2G_{n-2}-\dots-F_nG_0\\ &=G_n-F_2G_{n-2}-\dots-F_nG_0 \end{align}$$

So if we can prove that the last expression equals zero, we are done. And indeed,

$$\begin{align}\\ G_n &= F_0 G_{n-1}+F_1 G_{n-2} + F_2G_{n-3}\dots + F_{n-1} G_0\\ &=F_0\left(\color{red}{F_0}G_{n-2}+\color{red}{F_1}G_{n-3}\dots+\color{red}{F_{n-2}}G_0\right)+\color{blue}{F_1} G_{n-2} +\color{blue}{F_2}G_{n-3} \dots + \color{blue}{F_{n-1}} G_0\\ &=(\color{red}{F_0}+\color{blue}{F_1})G_{n-2}+(\color{red}{F_1}+\color{blue}{F_2})G_{n-3}+\dots+(\color{red}{F_{n-2}}+\color{blue}{F_{n-1}})G_0\\ &=F_2G_{n-2}+F_3G_{n-3}+\dots+F_nG_0 \end{align}$$

Answer 2

Let $G(z) = \sum\limits_{n=0}^\infty G_n z^n$ and $F(z) = \sum\limits_{n=0}^\infty F_n z^n$ where $F_n = \text{Fib}_{n+1}$ is the $(n+1)^{th}$ Fibonacci number. In following set of recurrence relations,

$$G_{n+1} = F_0 G_n + F_1 G_{n-1} + \cdots + F_n G_0,$$

if one multiply the $n^{th}$ term by $z^n$ and sum over $n$, we get

$$\frac{G(z)-1}{z} = F(z)G(z)\quad\implies\quad G(z) = \frac{1}{1 - zF(z)}$$

It is well known $\displaystyle\;F(z) = \frac{1}{1-z-z^2}$, this leads to

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

This implies

$$\begin{align} & (1 - 2z - z^2)( G(z) - 1 ) = z\\ \iff & (1 -2z - z^2)(G_1 z + G_2 z^2 + G_3 z^3 + G_4 z^4 + \cdots ) = z\\ \iff & G_1 z + ( G_2 - 2 G_1 ) z^2 + (G_3 - 2 G_2 - G_1 ) z^3 + (G_4 - 2G_3 - G_2)z^4 + \cdots = z\\ \implies & G_{n+2} = 2G_{n+1} + G_{n}\quad\text{ for } n \ge 1 \end{align} $$

This matches the the recurrence relation in OEIS A215928. By brute force, one find

$$G_0, G_1, G_2, G_3, \ldots = 1, 1, 2, 5, \ldots$$

Since $G_n$ matches $A215928(n)$ for $n = 1, 2$, above recurrence relation guarantee $G_n = A215928(n)$ for all $n \ge 1$. It turns out $G_0 = A215928(0)$ too, but that is more of a coincidence.