Derivation of Fibonacci sequence by difference equation/Z transform

Question

I'm trying to derive the Fibonacci sequence. I have the following problem:

$$N(t) = N(t-1)+ N(t-2) \quad \quad \quad \quad (I)$$

With initial conditions $N(1) = 2$ and $N(2) = 3$. Using:

$$N(t+2) = N(t+1)+ N(t) $$

We get $N(0) = 1$, $N(-1)=1$ and $N(-2)=0$. Taking the Z transform on (I) we have:

$$ N_Z(z) = z^{-1}N_Z(z)+N(-1) + z^{-2}N_Z(z) + z^{-1}N(-1)+N(-2)$$ $$\therefore N_Z(z) = \frac{z^{-1}+1}{1-z^{-1}-z^{-2}} $$

This give me the wrong formula. I should get the binet formula when I take the inverse Z transform. Z trasform of N(t) should look like:

$$\therefore N_Z(z) = \frac{z^{-1}}{1-z^{-1}-z^{-2}} $$

Thanks!

Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence? — Jakobian, Aug 03 '18 at 15:14
$N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci. — Jakobian, Aug 03 '18 at 15:45
https://math.stackexchange.com/questions/279868/causal-inverse-z-transform-of-fibonacci — lab bhattacharjee, Aug 04 '18 at 07:24

score 1 · Accepted Answer · answered Aug 03 '18 at 16:01

Let $x_n=N(n)$. Then: $$ \forall z\in\Omega\subset\mathbb{C}\\ \sum\limits_{n=-2}^\infty (x_{n+2}-x_{n+1}-x_n)z^{-(n+2)}=0\\ \iff \sum\limits_{n=-2}^\infty x_{n+2}z^{-(n+2)}-z^{-1}\sum\limits_{n=-2}^\infty x_{n+1}z^{-(n+1)}-z^{-2}\sum\limits_{n=-2}^\infty x_nz^{-n}=0 \\ \iff -x_{-1}z^{-1}+\sum\limits_{n=-3}^\infty x_{n+2}z^{-(n+2)}-z^{-1}\sum\limits_{n=-2}^\infty x_{n+1}z^{-(n+1)}-z^{-2}\sum\limits_{n=-2}^\infty x_nz^{-n}=0 \\ \iff (1-z^{-1}-z^{-2})\sum\limits_{n=-1}^\infty x_nz^{-n}=z^{-1} \\ \iff \sum\limits_{n=-1}^\infty x_nz^{-n}=\frac{z^{-1}}{1-z^{-1}-z^{-2}} $$.

Derivation of Fibonacci sequence by difference equation/Z transform

1 Answers1