Derivation of Fibonacci sequence by difference equation/Z transform

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

1

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^-1N_Z(z)+N(-1) + z^-2N_Z(z) + z^-1N(-1)+N(-2)$$
$$therefore N_Z(z) = fracz^-1+11-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) = fracz^-11-z^-1-z^-2 $$

Thanks!

fibonacci-numbers z-transform

share|cite|improve this question

edited Aug 3 at 15:43

asked Aug 3 at 14:56

Felipe

557

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
  – Rumpelstiltskin
  Aug 3 at 15:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
  – Felipe
  Aug 3 at 15:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
  – Rumpelstiltskin
  Aug 3 at 15:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, your answer clarified my problem!
  – Felipe
  Aug 3 at 17:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  math.stackexchange.com/questions/279868/…
  – lab bhattacharjee
  Aug 4 at 7:24
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

1

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^-1N_Z(z)+N(-1) + z^-2N_Z(z) + z^-1N(-1)+N(-2)$$
$$therefore N_Z(z) = fracz^-1+11-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) = fracz^-11-z^-1-z^-2 $$

Thanks!

fibonacci-numbers z-transform

share|cite|improve this question

edited Aug 3 at 15:43

asked Aug 3 at 14:56

Felipe

557

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
  – Rumpelstiltskin
  Aug 3 at 15:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
  – Felipe
  Aug 3 at 15:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
  – Rumpelstiltskin
  Aug 3 at 15:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, your answer clarified my problem!
  – Felipe
  Aug 3 at 17:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  math.stackexchange.com/questions/279868/…
  – lab bhattacharjee
  Aug 4 at 7:24
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

1

up vote
0
down vote

favorite

1

1

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^-1N_Z(z)+N(-1) + z^-2N_Z(z) + z^-1N(-1)+N(-2)$$
$$therefore N_Z(z) = fracz^-1+11-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) = fracz^-11-z^-1-z^-2 $$

Thanks!

fibonacci-numbers z-transform

share|cite|improve this question

edited Aug 3 at 15:43

asked Aug 3 at 14:56

Felipe

557

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^-1N_Z(z)+N(-1) + z^-2N_Z(z) + z^-1N(-1)+N(-2)$$
$$therefore N_Z(z) = fracz^-1+11-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) = fracz^-11-z^-1-z^-2 $$

Thanks!

fibonacci-numbers z-transform

share|cite|improve this question

edited Aug 3 at 15:43

asked Aug 3 at 14:56

Felipe

557

share|cite|improve this question

share|cite|improve this question

edited Aug 3 at 15:43

edited Aug 3 at 15:43

edited Aug 3 at 15:43

asked Aug 3 at 14:56

Felipe

557

asked Aug 3 at 14:56

Felipe

557

asked Aug 3 at 14:56

Felipe

557

557

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
  – Rumpelstiltskin
  Aug 3 at 15:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
  – Felipe
  Aug 3 at 15:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
  – Rumpelstiltskin
  Aug 3 at 15:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, your answer clarified my problem!
  – Felipe
  Aug 3 at 17:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  math.stackexchange.com/questions/279868/…
  – lab bhattacharjee
  Aug 4 at 7:24
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
  – Rumpelstiltskin
  Aug 3 at 15:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
  – Felipe
  Aug 3 at 15:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
  – Rumpelstiltskin
  Aug 3 at 15:45
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks, your answer clarified my problem!
  – Felipe
  Aug 3 at 17:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  math.stackexchange.com/questions/279868/…
  – lab bhattacharjee
  Aug 4 at 7:24
  

  
  
  
  

Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
– Rumpelstiltskin
Aug 3 at 15:14

Im not familiar with z-transform, but maybe it's because it's not an actual Fibonacci sequence?
– Rumpelstiltskin
Aug 3 at 15:14

The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
– Felipe
Aug 3 at 15:42

The fibonacci sequence isnt $N(t) = N(t-1)+N(t-2)$?
– Felipe
Aug 3 at 15:42

$N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
– Rumpelstiltskin
Aug 3 at 15:45

$N(1)=1$, $N(2)=1$ would be Fibonacci, this one is "shifted" Fibonacci.
– Rumpelstiltskin
Aug 3 at 15:45

Thanks, your answer clarified my problem!
– Felipe
Aug 3 at 17:15

Thanks, your answer clarified my problem!
– Felipe
Aug 3 at 17:15

math.stackexchange.com/questions/279868/…
– lab bhattacharjee
Aug 4 at 7:24

math.stackexchange.com/questions/279868/…
– lab bhattacharjee
Aug 4 at 7:24

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote

Let $x_n=N(n)$. Then:
$$
forall zinOmegasubsetmathbbC\
sumlimits_n=-2^infty (x_n+2-x_n+1-x_n)z^-(n+2)=0\
iff sumlimits_n=-2^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff -x_-1z^-1+sumlimits_n=-3^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff (1-z^-1-z^-2)sumlimits_n=-1^infty x_nz^-n=z^-1 \
iff sumlimits_n=-1^infty x_nz^-n=fracz^-11-z^-1-z^-2
$$.

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871167%2fderivation-of-fibonacci-sequence-by-difference-equation-z-transform%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

Let $x_n=N(n)$. Then:
$$
forall zinOmegasubsetmathbbC\
sumlimits_n=-2^infty (x_n+2-x_n+1-x_n)z^-(n+2)=0\
iff sumlimits_n=-2^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff -x_-1z^-1+sumlimits_n=-3^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff (1-z^-1-z^-2)sumlimits_n=-1^infty x_nz^-n=z^-1 \
iff sumlimits_n=-1^infty x_nz^-n=fracz^-11-z^-1-z^-2
$$.

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

add a comment | 

up vote
1
down vote

Let $x_n=N(n)$. Then:
$$
forall zinOmegasubsetmathbbC\
sumlimits_n=-2^infty (x_n+2-x_n+1-x_n)z^-(n+2)=0\
iff sumlimits_n=-2^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff -x_-1z^-1+sumlimits_n=-3^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff (1-z^-1-z^-2)sumlimits_n=-1^infty x_nz^-n=z^-1 \
iff sumlimits_n=-1^infty x_nz^-n=fracz^-11-z^-1-z^-2
$$.

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

add a comment | 

up vote
1
down vote

up vote
1
down vote

Let $x_n=N(n)$. Then:
$$
forall zinOmegasubsetmathbbC\
sumlimits_n=-2^infty (x_n+2-x_n+1-x_n)z^-(n+2)=0\
iff sumlimits_n=-2^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff -x_-1z^-1+sumlimits_n=-3^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff (1-z^-1-z^-2)sumlimits_n=-1^infty x_nz^-n=z^-1 \
iff sumlimits_n=-1^infty x_nz^-n=fracz^-11-z^-1-z^-2
$$.

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

Let $x_n=N(n)$. Then:
$$
forall zinOmegasubsetmathbbC\
sumlimits_n=-2^infty (x_n+2-x_n+1-x_n)z^-(n+2)=0\
iff sumlimits_n=-2^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff -x_-1z^-1+sumlimits_n=-3^infty x_n+2z^-(n+2)-z^-1sumlimits_n=-2^infty x_n+1z^-(n+1)-z^-2sumlimits_n=-2^infty x_nz^-n=0 \
iff (1-z^-1-z^-2)sumlimits_n=-1^infty x_nz^-n=z^-1 \
iff sumlimits_n=-1^infty x_nz^-n=fracz^-11-z^-1-z^-2
$$.

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

share|cite|improve this answer

share|cite|improve this answer

answered Aug 3 at 16:01

Quantic_Solver

214

answered Aug 3 at 16:01

Quantic_Solver

214

answered Aug 3 at 16:01

Quantic_Solver

214

214

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871167%2fderivation-of-fibonacci-sequence-by-difference-equation-z-transform%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email