Every $k$th Fibonacci generating function
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
To get the generating function of $F_n$, I use the basic recurrence $F_n = F_n-1 + F_n-2$.
I think the same approach will work for $F_kn$. For example,
$$F_2n = 3F_2(n-1) - F_2(n-2)$$
$$F_3n = 4F_3(n-1) + F_3(n-2)$$
from A001519 and A014445. I conjecture for any $k$:
$$F_kn = aF_k(n-1) + bF_k(n-2)$$
How can I find $a$ and $b$? My ideas were to try Binet's Formula (though that requires dealing with irrational numbers) and the matrix form
$$A^n = beginbmatrix 1 & 1 \ 1 & 0 endbmatrix^n = beginbmatrix F_n+1 & F_n \ F_n & F_n-1 endbmatrix$$ so that
$A^kn = aA^k(n-1) + bA^k(n-2) $.
Since $A$ is invertible this is equivalent to $A^2k = aA^k + bI$. Maybe this can be solved from here?
recurrence-relations generating-functions fibonacci-numbers
asked Jun 3 at 17:23
qwr
6,44842654
add a comment |Â
up vote
4
down vote
favorite
To get the generating function of $F_n$, I use the basic recurrence $F_n = F_n-1 + F_n-2$.
I think the same approach will work for $F_kn$. For example,
$$F_2n = 3F_2(n-1) - F_2(n-2)$$
$$F_3n = 4F_3(n-1) + F_3(n-2)$$
from A001519 and A014445. I conjecture for any $k$:
$$F_kn = aF_k(n-1) + bF_k(n-2)$$
How can I find $a$ and $b$? My ideas were to try Binet's Formula (though that requires dealing with irrational numbers) and the matrix form
$$A^n = beginbmatrix 1 & 1 \ 1 & 0 endbmatrix^n = beginbmatrix F_n+1 & F_n \ F_n & F_n-1 endbmatrix$$ so that
$A^kn = aA^k(n-1) + bA^k(n-2) $.
Since $A$ is invertible this is equivalent to $A^2k = aA^k + bI$. Maybe this can be solved from here?
recurrence-relations generating-functions fibonacci-numbers
asked Jun 3 at 17:23
qwr
6,44842654
1
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
To get the generating function of $F_n$, I use the basic recurrence $F_n = F_n-1 + F_n-2$.
I think the same approach will work for $F_kn$. For example,
$$F_2n = 3F_2(n-1) - F_2(n-2)$$
$$F_3n = 4F_3(n-1) + F_3(n-2)$$
from A001519 and A014445. I conjecture for any $k$:
$$F_kn = aF_k(n-1) + bF_k(n-2)$$
How can I find $a$ and $b$? My ideas were to try Binet's Formula (though that requires dealing with irrational numbers) and the matrix form
$$A^n = beginbmatrix 1 & 1 \ 1 & 0 endbmatrix^n = beginbmatrix F_n+1 & F_n \ F_n & F_n-1 endbmatrix$$ so that
$A^kn = aA^k(n-1) + bA^k(n-2) $.
Since $A$ is invertible this is equivalent to $A^2k = aA^k + bI$. Maybe this can be solved from here?
recurrence-relations generating-functions fibonacci-numbers
asked Jun 3 at 17:23
qwr
6,44842654
To get the generating function of $F_n$, I use the basic recurrence $F_n = F_n-1 + F_n-2$.
I think the same approach will work for $F_kn$. For example,
$$F_2n = 3F_2(n-1) - F_2(n-2)$$
$$F_3n = 4F_3(n-1) + F_3(n-2)$$
from A001519 and A014445. I conjecture for any $k$:
$$F_kn = aF_k(n-1) + bF_k(n-2)$$
How can I find $a$ and $b$? My ideas were to try Binet's Formula (though that requires dealing with irrational numbers) and the matrix form
$$A^n = beginbmatrix 1 & 1 \ 1 & 0 endbmatrix^n = beginbmatrix F_n+1 & F_n \ F_n & F_n-1 endbmatrix$$ so that
$A^kn = aA^k(n-1) + bA^k(n-2) $.
Since $A$ is invertible this is equivalent to $A^2k = aA^k + bI$. Maybe this can be solved from here?
recurrence-relations generating-functions fibonacci-numbers
asked Jun 3 at 17:23
qwr
6,44842654
edited Aug 22 at 7:15
asked Jun 3 at 17:23
qwr
6,44842654
asked Jun 3 at 17:23
qwr
6,44842654
asked Jun 3 at 17:23
qwr
6,44842654
6,44842654
1
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40
add a comment |Â
1
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40
1
1
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Binet's formula states that $F_n=alphatau^n+betatau'^n$
where $tau=frac12(1+sqrt5)$ and $tau'=frac12(-1+sqrt5)$.
Here it's immaterial what $alpha $ and $beta $ are.
Therefore
$$F_kn=alpha(tau^k)^n+beta(tau'^k)^n.$$
The recurrence for $F_kn$ has characteristic equation
$$(X-tau^k)(X-tau'^k)=X^2-(tau^k+tau'^k)X+tau^ktau'^k.$$
But $tau^ktau'^k=(-1)^k$ and $tau^k+tau'^k=L_k$, the $k$-th
Lucas number. ($L_0=2$, $L_1=1$, $L_n=L_n-1+L_n-2$).
Therefore
$$F_kn=L_kF_k(n-1)-(-1)^kF_k(n-2).$$
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Binet's formula states that $F_n=alphatau^n+betatau'^n$
where $tau=frac12(1+sqrt5)$ and $tau'=frac12(-1+sqrt5)$.
Here it's immaterial what $alpha $ and $beta $ are.
Therefore
$$F_kn=alpha(tau^k)^n+beta(tau'^k)^n.$$
The recurrence for $F_kn$ has characteristic equation
$$(X-tau^k)(X-tau'^k)=X^2-(tau^k+tau'^k)X+tau^ktau'^k.$$
But $tau^ktau'^k=(-1)^k$ and $tau^k+tau'^k=L_k$, the $k$-th
Lucas number. ($L_0=2$, $L_1=1$, $L_n=L_n-1+L_n-2$).
Therefore
$$F_kn=L_kF_k(n-1)-(-1)^kF_k(n-2).$$
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
add a comment |Â
up vote
2
down vote
accepted
Binet's formula states that $F_n=alphatau^n+betatau'^n$
where $tau=frac12(1+sqrt5)$ and $tau'=frac12(-1+sqrt5)$.
Here it's immaterial what $alpha $ and $beta $ are.
Therefore
$$F_kn=alpha(tau^k)^n+beta(tau'^k)^n.$$
The recurrence for $F_kn$ has characteristic equation
$$(X-tau^k)(X-tau'^k)=X^2-(tau^k+tau'^k)X+tau^ktau'^k.$$
But $tau^ktau'^k=(-1)^k$ and $tau^k+tau'^k=L_k$, the $k$-th
Lucas number. ($L_0=2$, $L_1=1$, $L_n=L_n-1+L_n-2$).
Therefore
$$F_kn=L_kF_k(n-1)-(-1)^kF_k(n-2).$$
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Binet's formula states that $F_n=alphatau^n+betatau'^n$
where $tau=frac12(1+sqrt5)$ and $tau'=frac12(-1+sqrt5)$.
Here it's immaterial what $alpha $ and $beta $ are.
Therefore
$$F_kn=alpha(tau^k)^n+beta(tau'^k)^n.$$
The recurrence for $F_kn$ has characteristic equation
$$(X-tau^k)(X-tau'^k)=X^2-(tau^k+tau'^k)X+tau^ktau'^k.$$
But $tau^ktau'^k=(-1)^k$ and $tau^k+tau'^k=L_k$, the $k$-th
Lucas number. ($L_0=2$, $L_1=1$, $L_n=L_n-1+L_n-2$).
Therefore
$$F_kn=L_kF_k(n-1)-(-1)^kF_k(n-2).$$
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
Binet's formula states that $F_n=alphatau^n+betatau'^n$
where $tau=frac12(1+sqrt5)$ and $tau'=frac12(-1+sqrt5)$.
Here it's immaterial what $alpha $ and $beta $ are.
Therefore
$$F_kn=alpha(tau^k)^n+beta(tau'^k)^n.$$
The recurrence for $F_kn$ has characteristic equation
$$(X-tau^k)(X-tau'^k)=X^2-(tau^k+tau'^k)X+tau^ktau'^k.$$
But $tau^ktau'^k=(-1)^k$ and $tau^k+tau'^k=L_k$, the $k$-th
Lucas number. ($L_0=2$, $L_1=1$, $L_n=L_n-1+L_n-2$).
Therefore
$$F_kn=L_kF_k(n-1)-(-1)^kF_k(n-2).$$
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
answered Jun 3 at 17:52
Lord Shark the Unknown
88k954115
88k954115
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
add a comment |Â
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
How did you obtain the characteristic equation?
– qwr
Jun 3 at 22:06
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
No, I hid that in the $alpha$ and $beta$. @lhf
– Lord Shark the Unknown
Jun 12 at 16:38
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
I just found out this is listed as the "multiple-angle recurrence" on Mathworld mathworld.wolfram.com/FibonacciNumber.html
– qwr
Aug 23 at 4:39
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2806811%2fevery-kth-fibonacci-generating-function%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Just computing a few terms it seems $a_k = (-1)^k+1$ and $b_k= 1,3,4,7,11,ldots$ so $b_k$ satisfy the Fibonacci recurrsion $b_k+1 = b_k + b_k-1$ with $b_1 = 1$ and $b_2 = 3$.
– Winther
Jun 3 at 17:40