closed-form expression for nth term of the Fibonacci sequence

Generally we all know what a Fibonacci series is. I had 1st seen it in my computer science class where I used the recursive relation to find nth term of Fibonacci series, when I was 1st taught recursive functions. Today my friend told me that he solved the recurrence using power series method to get the golden ratio's and the relation. So I also wanted to write about it and derive the same with z-transform which I learned in my DSP class, one of the few classes I read the books of. So here we are and lets get started.

So lets see the Fibonacci series first...

1,1,2,3,5,8,13,.....

If y(n) be the nth term of the Fibonacci sequence then the recurrence relation below clearly satisfies the relation below...
y(n) = y(n-1) + y(n-2)            --------------(1)

we also have 2 initial conditions:
1) y(0) = y(-1) + y(-2) = 1
2) y(1) = y(0)  + y(-1) = 1

from these conditions we see that y(-1) = 0 and y(-2)=1 work this out and make sure u get this.

 To take the z-transform of the eq. (1) we need to know about one-sided or unilateral z-transform. Its not very different from two-sided z-transform. Its just that in two-sided z-transform needs signal to be specified in the range (-∞,∞). Since input is applied at a finite time sequence say n₀ therefore we need signal to be specified in the range [n0,∞).

The unilateral or one-sided z-transform may be defined as:

 and the time shifting property is also a bit different just a bit modified and can be intuitively proved.Which I am not going to do here.
TIME DELAY PROPERTY:

Taking z-transform by applying time delay property,  we get..

Y(z) = [z^-1 Y(z) + y(-1)]  + [z^-2Y(z) + y(-2) + y(-1)z^-1]

 or

Y(z) = 1/(1 - z^-1 - z^-2)

or

Y(z) = z²/(z² – z¹ -1)

or 

Y(z) = z²/(z - p₁)(z - p₂)        where p₁=(1 + √5)/2     and     p₂=(1 – √5)/2

or 

Y(z) = 1/(1 - p₁ z^-1)(1 - p₂ z^-1)

using partial fraction, we get :

 

Y(z) = A₁/(1 - p₁ z^-1)  +  A₂/(1 - p₂ z^-1)

where A₁ = 1/(1 – p₂p₁^-1) = p₁/(p₁ – p₂) = p₁ / √5

and     A2 = 1/(1 – p₁p₂^-1) = p₂/(p₂ – p₁) = -p₂ / √5

 Now we know that or can be easily verified that:

UZ(aⁿ u(n)) = 1/(1 – az^-1)  where UZ(.) is unilateral z-transform

so we finally get, 

y(n) = [A₁(p₁)ⁿ   + A₂(p₂)ⁿ ]u(n)

substituting A1 and A2 we get:

                                                   

 y(n) = (1/√5)[(p₁)ⁿ⁺¹   - (p₂)ⁿ⁺¹ ]u(n)    ---------------(2)

 y(n) = (1/√5)[(p₁)ⁿ⁺¹   - ( p_{1_conjugate})ⁿ⁺¹ ]u(n)  
 where p₁=(1 + √5)/2     and     p₂ = p_{1_conjugate}=(1 – √5)/2
 
equation (2) above is the formula which works as nth term of Fibonacci series.