Fibonacci numbers with even index

242 Views Asked by At

$a_{0}=1, a_{n}=a_{n-1}+2a_{n-2}+\ldots+na_{n-n}$

We can see that $a_{n}=\sum_{m=0}^{n}{ma_{n-m}}$.

Then $G(z)=1+\sum_{n=1}^\infty (\sum_{m=0}^n{ma_{n-m}) \cdot z^n = 1+\sum_{n=0}^\infty(\sum_{m=0}^n ma_{n-m}) \cdot z^n}$. As we know that if we have $c_n=\sum_{m=0}^n ma_{n-m}$, then $c_n$ is generated by the $G(z)H(z)$, where $G(z)$ generates $b_n=n$ and $H(z)$ generates $a_{n}$. So, let's denote $H(z)$ as a generating function of $a_n$.

We can evaluate $G(z)=\frac{z}{(1-z)^2}$, then $H(z)=H(z)\left(\frac{z}{(1-z)^2}\right)+1$, so we establish that $$H(z)=\frac{z^2+1}{z^2+z+1}.$$

But on the other hand, if we calculate the first $a_n$ numbers, then we can assume that the sequence consists of the Fibonacci numbers with even index(apart from the $a_{0}=1$). So it's reasonable to suggest that $G(z)=\frac{1}{2}(\frac{z}{1-z-z^{2}}-\frac{z}{1+z-z^2})+1$. Actually, this doesn't correspond to the generating function, which was evaluated by the different approach.

Could somebody tell me, what's wrong with the first attempt? Would be greatful to recieve any piece of advice.

1

There are 1 best solutions below

0
On

There are a couple of reasons for the mismatch. First, you solved the equation

$$H(z)=H(z)\left(\frac{z}{(1-z)^2}\right)+1\tag{1}$$

incorrectly for $H(z)$: $(1)$ yields

$$H(z)\left(1-\frac{z}{(1-z)^2}\right)=1\;,$$

so

$$\begin{align*} H(z)&=\frac{1}{1-\frac{z}{(1-z)^2}}\\\\ &=\frac{(1-z)^2}{(1-z)^2-z}\\\\ &=1+\frac{z}{1-3x-z^2}\;. \end{align*}$$

Secondly,

$$\frac12\left(\frac{z}{1-z-z^2}-\frac{z}{1+z-z^2}\right)=\sum_{n\ge 0}F_{2n}z^{2n}\;,$$

and you want

$$1+\sum_{n\ge 0}F_{2n}z^n\;.$$