Say the Fibonacci sequence is defined by:

$y(n) = y(n-1) + y(n-2)$

initial conditions: $y(0)=0, y(1)=1$

I incorporate those initial conditions as:

$y(n) = y(n-1) + y(n-2) + \delta(n-1)$

I compute the z-transform as:

$Y(z) = z^{-1}Y(z) + z^{-2}Y(z) + z^{-1}$

solve for $Y(z)$:

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

Now I am having the hardest time taking the causal inverse z-transform. Any tips?


Using partial fraction techniques and denoting the zeroes of $z^2-z-1$ by $\alpha_1$ and $\alpha_2$, we have

$$ Y(z) = \frac{z}{z^2-z-1} \implies \frac{Y(z)}{z} = \left(-\frac{1}{5}+\frac{2}{5}\alpha_1\right) \frac{1}{z-\alpha_1}+ \left(-\frac{1}{5}+\frac{2}{5}\alpha_2\right) \frac{1}{z-\alpha_2} $$

$$ \implies Y(z) = \beta_1 \frac{z}{z-\alpha_1}+\beta_2 \frac{z}{z-\alpha_2} $$

$$ \implies Y(z) = \beta_1\left(1-\frac{\alpha_1}{z}\right)^{-1}+\beta_2\left(1-\frac{\alpha_2}{z}\right)^{-1} $$

where $\beta_1 =\left(-\frac{1}{5}+\frac{2}{5}\alpha_1\right)$ and $\beta_2=\left(-\frac{1}{5}+\frac{2}{5}\alpha_2\right)$.

$$ \implies Y(z) = \beta_1 \sum_{n=0}^{\infty}\frac{\alpha_1^n}{z^n}+\beta_2 \sum_{n=0}^{\infty}\frac{\alpha_2^n}{z^n}$$

$$ \implies y(n)= \beta_1\alpha_1^n + \beta_2\alpha_2^n . $$

Note: You can use the inverse Z-transform formula which uses the contour integration

$$ y(n)=\frac{1}{2\pi i}\int_{C} z^{k-1}Y(z) dz .$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.