The sum of any ten consecutive numbers from a fibonacci sequence is divisible by 11 [closed]
$begingroup$
How do I prove that any ten consecutive numbers of a fibonacci sequence is divisible by 11?
divisibility fibonacci-numbers
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
closed as off-topic by Javi, Mike Pierce, John Douma, YiFan, heropup Apr 2 at 2:31
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Javi, Mike Pierce, John Douma, YiFan, heropup
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
How do I prove that any ten consecutive numbers of a fibonacci sequence is divisible by 11?
divisibility fibonacci-numbers
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
closed as off-topic by Javi, Mike Pierce, John Douma, YiFan, heropup Apr 2 at 2:31
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Javi, Mike Pierce, John Douma, YiFan, heropup
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
1
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25
add a comment |
$begingroup$
How do I prove that any ten consecutive numbers of a fibonacci sequence is divisible by 11?
divisibility fibonacci-numbers
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
How do I prove that any ten consecutive numbers of a fibonacci sequence is divisible by 11?
divisibility fibonacci-numbers
divisibility fibonacci-numbers
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 1 at 14:10
AbigailAbigail
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 1 at 14:10
AbigailAbigail
171
asked Apr 1 at 14:10
AbigailAbigail
171
171
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Abigail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
closed as off-topic by Javi, Mike Pierce, John Douma, YiFan, heropup Apr 2 at 2:31
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Javi, Mike Pierce, John Douma, YiFan, heropup
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Javi, Mike Pierce, John Douma, YiFan, heropup Apr 2 at 2:31
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Javi, Mike Pierce, John Douma, YiFan, heropup
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
1
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25
add a comment |
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
1
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
1
1
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suggestion:
If the first two numbers in the sequences are $a, b$, then you can use the Fibonacci recursion to generate the next $8$ numbers. Then add them all up and see what you get. (Your answer will be in terms of $a$ and $b$.)
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
$endgroup$
9
$begingroup$
For the lazy, the sum is55a + 88b. ;)
$endgroup$
– Mukul Gupta
Apr 1 at 19:14
add a comment |
$begingroup$
If you use a Binet-like formula for the Fibonacci sequence $mod 11$, you'll notice that $$F_nequiv 8cdot (4^n-(-3)^n)pmod{11}$$
And thus $$sum_{k=0}^{9} F_{n+k}equiv8cdot 4^ncdot(-7)cdot(4^{10}-1)-8cdot3^ncdot8cdot((-3)^{10}-1)pmod{11}$$
By Fermat's theorem, $a^{10}equiv1pmod {11}$ for all $anotequiv0pmod{11}$.
More generally, the sum of $p-1$ consecutive Fibonacci numbers is divisible by the prime $p$ as soon as the polynomial $x^2-x-1$ is reducible in $Bbb F_p[x]$ (and $1$ is not a root, which can never occur).
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
$endgroup$
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suggestion:
If the first two numbers in the sequences are $a, b$, then you can use the Fibonacci recursion to generate the next $8$ numbers. Then add them all up and see what you get. (Your answer will be in terms of $a$ and $b$.)
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
$endgroup$
9
$begingroup$
For the lazy, the sum is55a + 88b. ;)
$endgroup$
– Mukul Gupta
Apr 1 at 19:14
add a comment |
$begingroup$
Suggestion:
If the first two numbers in the sequences are $a, b$, then you can use the Fibonacci recursion to generate the next $8$ numbers. Then add them all up and see what you get. (Your answer will be in terms of $a$ and $b$.)
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
$endgroup$
9
$begingroup$
For the lazy, the sum is55a + 88b. ;)
$endgroup$
– Mukul Gupta
Apr 1 at 19:14
add a comment |
$begingroup$
Suggestion:
If the first two numbers in the sequences are $a, b$, then you can use the Fibonacci recursion to generate the next $8$ numbers. Then add them all up and see what you get. (Your answer will be in terms of $a$ and $b$.)
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
$endgroup$
Suggestion:
If the first two numbers in the sequences are $a, b$, then you can use the Fibonacci recursion to generate the next $8$ numbers. Then add them all up and see what you get. (Your answer will be in terms of $a$ and $b$.)
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
answered Apr 1 at 14:16
paw88789paw88789
29.7k12351
29.7k12351
9
$begingroup$
For the lazy, the sum is55a + 88b. ;)
$endgroup$
– Mukul Gupta
Apr 1 at 19:14
add a comment |
9
$begingroup$
For the lazy, the sum is55a + 88b. ;)
$endgroup$
– Mukul Gupta
Apr 1 at 19:14
9
9
$begingroup$
For the lazy, the sum is
55a + 88b. ;)$endgroup$
– Mukul Gupta
Apr 1 at 19:14
$begingroup$
For the lazy, the sum is
55a + 88b. ;)$endgroup$
– Mukul Gupta
Apr 1 at 19:14
add a comment |
$begingroup$
If you use a Binet-like formula for the Fibonacci sequence $mod 11$, you'll notice that $$F_nequiv 8cdot (4^n-(-3)^n)pmod{11}$$
And thus $$sum_{k=0}^{9} F_{n+k}equiv8cdot 4^ncdot(-7)cdot(4^{10}-1)-8cdot3^ncdot8cdot((-3)^{10}-1)pmod{11}$$
By Fermat's theorem, $a^{10}equiv1pmod {11}$ for all $anotequiv0pmod{11}$.
More generally, the sum of $p-1$ consecutive Fibonacci numbers is divisible by the prime $p$ as soon as the polynomial $x^2-x-1$ is reducible in $Bbb F_p[x]$ (and $1$ is not a root, which can never occur).
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
$endgroup$
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
add a comment |
$begingroup$
If you use a Binet-like formula for the Fibonacci sequence $mod 11$, you'll notice that $$F_nequiv 8cdot (4^n-(-3)^n)pmod{11}$$
And thus $$sum_{k=0}^{9} F_{n+k}equiv8cdot 4^ncdot(-7)cdot(4^{10}-1)-8cdot3^ncdot8cdot((-3)^{10}-1)pmod{11}$$
By Fermat's theorem, $a^{10}equiv1pmod {11}$ for all $anotequiv0pmod{11}$.
More generally, the sum of $p-1$ consecutive Fibonacci numbers is divisible by the prime $p$ as soon as the polynomial $x^2-x-1$ is reducible in $Bbb F_p[x]$ (and $1$ is not a root, which can never occur).
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
$endgroup$
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
add a comment |
$begingroup$
If you use a Binet-like formula for the Fibonacci sequence $mod 11$, you'll notice that $$F_nequiv 8cdot (4^n-(-3)^n)pmod{11}$$
And thus $$sum_{k=0}^{9} F_{n+k}equiv8cdot 4^ncdot(-7)cdot(4^{10}-1)-8cdot3^ncdot8cdot((-3)^{10}-1)pmod{11}$$
By Fermat's theorem, $a^{10}equiv1pmod {11}$ for all $anotequiv0pmod{11}$.
More generally, the sum of $p-1$ consecutive Fibonacci numbers is divisible by the prime $p$ as soon as the polynomial $x^2-x-1$ is reducible in $Bbb F_p[x]$ (and $1$ is not a root, which can never occur).
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
$endgroup$
If you use a Binet-like formula for the Fibonacci sequence $mod 11$, you'll notice that $$F_nequiv 8cdot (4^n-(-3)^n)pmod{11}$$
And thus $$sum_{k=0}^{9} F_{n+k}equiv8cdot 4^ncdot(-7)cdot(4^{10}-1)-8cdot3^ncdot8cdot((-3)^{10}-1)pmod{11}$$
By Fermat's theorem, $a^{10}equiv1pmod {11}$ for all $anotequiv0pmod{11}$.
More generally, the sum of $p-1$ consecutive Fibonacci numbers is divisible by the prime $p$ as soon as the polynomial $x^2-x-1$ is reducible in $Bbb F_p[x]$ (and $1$ is not a root, which can never occur).
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
edited Apr 2 at 2:06
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
answered Apr 1 at 14:46
Saucy O'PathSaucy O'Path
6,4671627
6,4671627
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
add a comment |
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
4
4
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
I can't help but read that as "for all values of 11 which do not divide a".
$endgroup$
– hobbs
Apr 1 at 20:41
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@hobbs Agreed; $ainBbb Zsetminus 11Bbb Z$ would be better.
$endgroup$
– J.G.
Apr 1 at 20:59
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@J.G. ... or $anotequiv0pmod{11}$, for that matter.
$endgroup$
– Saucy O'Path
Apr 1 at 21:00
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
$begingroup$
@SaucyO'Path It'd certainly be more consistent with the rest of your formalism. You may as well edit it in, then.
$endgroup$
– J.G.
Apr 1 at 21:01
add a comment |
$begingroup$
I mean, just bash? Use the recursive formula to show it.
$endgroup$
– Don Thousand
Apr 1 at 14:12
1
$begingroup$
See also here: math.stackexchange.com/questions/60049/…
$endgroup$
– Jonas Lenz
Apr 1 at 14:12
$begingroup$
How about using artofproblemsolving.com/wiki/index.php?title=Binet%27s_Formula
$endgroup$
– lab bhattacharjee
Apr 1 at 14:21
$begingroup$
Possible duplicate of Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?
$endgroup$
– Quuxplusone
Apr 1 at 21:25