Proof that Sylvester numbers, when reduced modulo 864 , form an arithmetic progression...
up vote
1
down vote
favorite
The following observation has been made:
Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$
This has been checked for the first ten members of the sequence:
$$7≡7(mod864)$$
$$43≡43(mod864)$$
$$1807≡79(mod864)$$
$$3263443≡115(mod864)$$
$$10650056950807≡151(mod864)$$
$$113423713055421844361000443≡187(mod864)$$
$$12864938683278671740537145998360961546653259485195807≡223(mod864)$$
I have been unable to check other numbers in this sequence, due to the rapid growth of the sequence, the numbers become too large to handle.
However, we can use congruence relations, congruence arithmetic and arithmetic of residue classes to prove that Sylvester numbers ,when reduced $modulo 864$, form an arithmetic progression.
Consider the following:
One may define the sequence by the recurrence relation:
$$si=si−1(si−1−1)+1$$
Sylvester's sequence can also be defined by the formula:
$$sn=1+∏n−1i=0si$$
$$7≡7 (mod864)$$
$$7x6+1=43≡43 (mod864)$$
$$43x42+1=1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
$$115x114+1=13111≡151 (mod 864)$$
$$151x150+1=22651≡187 (mod 864)$$
$$187x186+1=34783≡223 (mod 864)$$
$$223x222+1=49507≡259 (mod 864)$$
$$259x258+1=66823≡295 (mod 864)$$
$$295x294+1=86731≡331 (mod 864)$$
$$331x330+1=109231≡367 (mod 864)$$
$$367x366+1=134323≡403 (mod 864)$$
$$403x402+1=162007≡439 (mod 864)$$
$$439x438+1=192283≡475 (mod 864)$$
$$475x474+1=225151≡511 (mod 864)$$
$$511x510+1=260611≡547 (mod 864)$$
$$547x546+1=298663≡583 (mod 864)$$
$$583x582+1=339307≡619 (mod 864)$$
$$619x618+1=382543≡655 (mod 864)$$
$$655x654+1=428371≡691 (mod 864)$$
$$691x690+1=476791≡727 (mod 864)$$
$$727x726+1=527803≡763 (mod 864)$$
$$763x762+1=581407≡799 (mod 864)$$
$$799x798+1=637603≡835 (mod 864)$$
$$835x834+1=696391≡7 (mod 864)$$
$$7x6+1 =43≡43 (mod 864)$$
$$43x42+1 =1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
etc.
Notice that after $24$ cycles , we get back to where we started. Hence Sylvester numbers , reduced $modulo 864$ form an arithmetic progression of $24$ terms which will then repeat until infinity. Therefore Sylvester sequence , reduced $mod 864$, forms an arithmetic progression of $24$ terms, which will repeat until infinity.
QED
sequences-and-series elementary-number-theory modular-arithmetic
add a comment |
up vote
1
down vote
favorite
The following observation has been made:
Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$
This has been checked for the first ten members of the sequence:
$$7≡7(mod864)$$
$$43≡43(mod864)$$
$$1807≡79(mod864)$$
$$3263443≡115(mod864)$$
$$10650056950807≡151(mod864)$$
$$113423713055421844361000443≡187(mod864)$$
$$12864938683278671740537145998360961546653259485195807≡223(mod864)$$
I have been unable to check other numbers in this sequence, due to the rapid growth of the sequence, the numbers become too large to handle.
However, we can use congruence relations, congruence arithmetic and arithmetic of residue classes to prove that Sylvester numbers ,when reduced $modulo 864$, form an arithmetic progression.
Consider the following:
One may define the sequence by the recurrence relation:
$$si=si−1(si−1−1)+1$$
Sylvester's sequence can also be defined by the formula:
$$sn=1+∏n−1i=0si$$
$$7≡7 (mod864)$$
$$7x6+1=43≡43 (mod864)$$
$$43x42+1=1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
$$115x114+1=13111≡151 (mod 864)$$
$$151x150+1=22651≡187 (mod 864)$$
$$187x186+1=34783≡223 (mod 864)$$
$$223x222+1=49507≡259 (mod 864)$$
$$259x258+1=66823≡295 (mod 864)$$
$$295x294+1=86731≡331 (mod 864)$$
$$331x330+1=109231≡367 (mod 864)$$
$$367x366+1=134323≡403 (mod 864)$$
$$403x402+1=162007≡439 (mod 864)$$
$$439x438+1=192283≡475 (mod 864)$$
$$475x474+1=225151≡511 (mod 864)$$
$$511x510+1=260611≡547 (mod 864)$$
$$547x546+1=298663≡583 (mod 864)$$
$$583x582+1=339307≡619 (mod 864)$$
$$619x618+1=382543≡655 (mod 864)$$
$$655x654+1=428371≡691 (mod 864)$$
$$691x690+1=476791≡727 (mod 864)$$
$$727x726+1=527803≡763 (mod 864)$$
$$763x762+1=581407≡799 (mod 864)$$
$$799x798+1=637603≡835 (mod 864)$$
$$835x834+1=696391≡7 (mod 864)$$
$$7x6+1 =43≡43 (mod 864)$$
$$43x42+1 =1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
etc.
Notice that after $24$ cycles , we get back to where we started. Hence Sylvester numbers , reduced $modulo 864$ form an arithmetic progression of $24$ terms which will then repeat until infinity. Therefore Sylvester sequence , reduced $mod 864$, forms an arithmetic progression of $24$ terms, which will repeat until infinity.
QED
sequences-and-series elementary-number-theory modular-arithmetic
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The following observation has been made:
Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$
This has been checked for the first ten members of the sequence:
$$7≡7(mod864)$$
$$43≡43(mod864)$$
$$1807≡79(mod864)$$
$$3263443≡115(mod864)$$
$$10650056950807≡151(mod864)$$
$$113423713055421844361000443≡187(mod864)$$
$$12864938683278671740537145998360961546653259485195807≡223(mod864)$$
I have been unable to check other numbers in this sequence, due to the rapid growth of the sequence, the numbers become too large to handle.
However, we can use congruence relations, congruence arithmetic and arithmetic of residue classes to prove that Sylvester numbers ,when reduced $modulo 864$, form an arithmetic progression.
Consider the following:
One may define the sequence by the recurrence relation:
$$si=si−1(si−1−1)+1$$
Sylvester's sequence can also be defined by the formula:
$$sn=1+∏n−1i=0si$$
$$7≡7 (mod864)$$
$$7x6+1=43≡43 (mod864)$$
$$43x42+1=1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
$$115x114+1=13111≡151 (mod 864)$$
$$151x150+1=22651≡187 (mod 864)$$
$$187x186+1=34783≡223 (mod 864)$$
$$223x222+1=49507≡259 (mod 864)$$
$$259x258+1=66823≡295 (mod 864)$$
$$295x294+1=86731≡331 (mod 864)$$
$$331x330+1=109231≡367 (mod 864)$$
$$367x366+1=134323≡403 (mod 864)$$
$$403x402+1=162007≡439 (mod 864)$$
$$439x438+1=192283≡475 (mod 864)$$
$$475x474+1=225151≡511 (mod 864)$$
$$511x510+1=260611≡547 (mod 864)$$
$$547x546+1=298663≡583 (mod 864)$$
$$583x582+1=339307≡619 (mod 864)$$
$$619x618+1=382543≡655 (mod 864)$$
$$655x654+1=428371≡691 (mod 864)$$
$$691x690+1=476791≡727 (mod 864)$$
$$727x726+1=527803≡763 (mod 864)$$
$$763x762+1=581407≡799 (mod 864)$$
$$799x798+1=637603≡835 (mod 864)$$
$$835x834+1=696391≡7 (mod 864)$$
$$7x6+1 =43≡43 (mod 864)$$
$$43x42+1 =1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
etc.
Notice that after $24$ cycles , we get back to where we started. Hence Sylvester numbers , reduced $modulo 864$ form an arithmetic progression of $24$ terms which will then repeat until infinity. Therefore Sylvester sequence , reduced $mod 864$, forms an arithmetic progression of $24$ terms, which will repeat until infinity.
QED
sequences-and-series elementary-number-theory modular-arithmetic
The following observation has been made:
Numbers in Sylvester's sequence,when reduced $modulo 864$, form an arithmetic progression, namely $$7,43,79,115,151,187,223,259,295,331,.....$$
This has been checked for the first ten members of the sequence:
$$7≡7(mod864)$$
$$43≡43(mod864)$$
$$1807≡79(mod864)$$
$$3263443≡115(mod864)$$
$$10650056950807≡151(mod864)$$
$$113423713055421844361000443≡187(mod864)$$
$$12864938683278671740537145998360961546653259485195807≡223(mod864)$$
I have been unable to check other numbers in this sequence, due to the rapid growth of the sequence, the numbers become too large to handle.
However, we can use congruence relations, congruence arithmetic and arithmetic of residue classes to prove that Sylvester numbers ,when reduced $modulo 864$, form an arithmetic progression.
Consider the following:
One may define the sequence by the recurrence relation:
$$si=si−1(si−1−1)+1$$
Sylvester's sequence can also be defined by the formula:
$$sn=1+∏n−1i=0si$$
$$7≡7 (mod864)$$
$$7x6+1=43≡43 (mod864)$$
$$43x42+1=1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
$$115x114+1=13111≡151 (mod 864)$$
$$151x150+1=22651≡187 (mod 864)$$
$$187x186+1=34783≡223 (mod 864)$$
$$223x222+1=49507≡259 (mod 864)$$
$$259x258+1=66823≡295 (mod 864)$$
$$295x294+1=86731≡331 (mod 864)$$
$$331x330+1=109231≡367 (mod 864)$$
$$367x366+1=134323≡403 (mod 864)$$
$$403x402+1=162007≡439 (mod 864)$$
$$439x438+1=192283≡475 (mod 864)$$
$$475x474+1=225151≡511 (mod 864)$$
$$511x510+1=260611≡547 (mod 864)$$
$$547x546+1=298663≡583 (mod 864)$$
$$583x582+1=339307≡619 (mod 864)$$
$$619x618+1=382543≡655 (mod 864)$$
$$655x654+1=428371≡691 (mod 864)$$
$$691x690+1=476791≡727 (mod 864)$$
$$727x726+1=527803≡763 (mod 864)$$
$$763x762+1=581407≡799 (mod 864)$$
$$799x798+1=637603≡835 (mod 864)$$
$$835x834+1=696391≡7 (mod 864)$$
$$7x6+1 =43≡43 (mod 864)$$
$$43x42+1 =1807≡79 (mod 864)$$
$$79x78+1=6163≡115 (mod 864)$$
etc.
Notice that after $24$ cycles , we get back to where we started. Hence Sylvester numbers , reduced $modulo 864$ form an arithmetic progression of $24$ terms which will then repeat until infinity. Therefore Sylvester sequence , reduced $mod 864$, forms an arithmetic progression of $24$ terms, which will repeat until infinity.
QED
sequences-and-series elementary-number-theory modular-arithmetic
sequences-and-series elementary-number-theory modular-arithmetic
edited Nov 18 at 3:20
AryanSonwatikar
819
819
asked Nov 16 at 20:54
Derek
1845
1845
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11
add a comment |
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
Hint:
If $$a_n=36n+7$$
then
$$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$
Now remains to study
$$(12n^2+13n+1)bmodfrac{864}{36}.$$
(Final hint, $12n(n+1)bmod24=0$.)
add a comment |
up vote
1
down vote
Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.
Notice $bmod 864!: a_n = 7! +! 36j Longrightarrow color{#0a0}{a_{n+1}},equiv, color{#0a0}{a_n}!+color{#c00}{36}, $ by
$underbrace{color{#0a0}{a_{n+1}!-!a_n} = (a_n!-!1)^2}_{Large a_{n+1} = a_n^2-a_n+1}! = (6!+!36j)^2! = 36+432,underbrace{j(1!+!3j)}_{large rm even}equiv color{#c00}{36}.,$
Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $, (1+b)^n = color{#0a0}{1+nb},pmod{!b^2}.,$ To make this clearer we examine the sequence $,b_n := a_n! - 1,,$ which satisfies $,b_{k+1} = b_k + b_k^2,, b_0 = 1.$
Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $,b_{k+1} = b_k(1+ b_k).,$ Then $$ b := b_{large k}, Rightarrow, b_{large k+n} equiv b(1+b)^nequiv b(color{#0a0}{1+nb}) pmod {!b^3}qquad $$
Proof $ $ By induction on $n$. Clear if $n=0.,$ Suppose for induction it is true for $n$. Then
$qquad begin{align}
bmod color{#c00}{b^3}!: b_{large j+n+1}, = &qquad, b_{large j+n} (1+b_{large j+n})\
= &, color{#c00}b(1+nb)(1+b+ncolor{#c00}{b^2)}\
equiv &, b(1+nb)(1+b) {rm by} color{#c00}bcolor{#c00}{b^2}equiv 0\
equiv &, b(1+(n!+!1)b)\
equiv &, b(1+b)^{large n+1}qquadqquadquad {bf QED}
end{align}qquadqquadqquad $
When $,b = 2!+!4iequiv 2pmod{!4}$ we can enlarge the modulus to $,4b^3$ since, as above
$quad begin{align}
bmod color{#c00}{4b^3}!: b_{j+n+1}
equiv &, b(1+(n!+!1)b) + color{#c00}2,{underbrace{n(1+nb/2}_{color{#c00}{rm even}})},color{#c00}{b^3}\[.2em]
end{align}qquadqquadqquad $
Here $,b_2 = 6,$ so we get $,b_{2+n}equiv 6 + 36npmod{!864},,$ just as you observed.
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Hint:
If $$a_n=36n+7$$
then
$$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$
Now remains to study
$$(12n^2+13n+1)bmodfrac{864}{36}.$$
(Final hint, $12n(n+1)bmod24=0$.)
add a comment |
up vote
1
down vote
Hint:
If $$a_n=36n+7$$
then
$$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$
Now remains to study
$$(12n^2+13n+1)bmodfrac{864}{36}.$$
(Final hint, $12n(n+1)bmod24=0$.)
add a comment |
up vote
1
down vote
up vote
1
down vote
Hint:
If $$a_n=36n+7$$
then
$$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$
Now remains to study
$$(12n^2+13n+1)bmodfrac{864}{36}.$$
(Final hint, $12n(n+1)bmod24=0$.)
Hint:
If $$a_n=36n+7$$
then
$$a_n^2-a_n+1=(36n+7)^2-(36n+7)+1=432n^2+468n+43=36(12n^2+13n+1)+7.$$
Now remains to study
$$(12n^2+13n+1)bmodfrac{864}{36}.$$
(Final hint, $12n(n+1)bmod24=0$.)
edited Nov 17 at 0:07
answered Nov 16 at 21:17
Yves Daoust
122k668217
122k668217
add a comment |
add a comment |
up vote
1
down vote
Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.
Notice $bmod 864!: a_n = 7! +! 36j Longrightarrow color{#0a0}{a_{n+1}},equiv, color{#0a0}{a_n}!+color{#c00}{36}, $ by
$underbrace{color{#0a0}{a_{n+1}!-!a_n} = (a_n!-!1)^2}_{Large a_{n+1} = a_n^2-a_n+1}! = (6!+!36j)^2! = 36+432,underbrace{j(1!+!3j)}_{large rm even}equiv color{#c00}{36}.,$
Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $, (1+b)^n = color{#0a0}{1+nb},pmod{!b^2}.,$ To make this clearer we examine the sequence $,b_n := a_n! - 1,,$ which satisfies $,b_{k+1} = b_k + b_k^2,, b_0 = 1.$
Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $,b_{k+1} = b_k(1+ b_k).,$ Then $$ b := b_{large k}, Rightarrow, b_{large k+n} equiv b(1+b)^nequiv b(color{#0a0}{1+nb}) pmod {!b^3}qquad $$
Proof $ $ By induction on $n$. Clear if $n=0.,$ Suppose for induction it is true for $n$. Then
$qquad begin{align}
bmod color{#c00}{b^3}!: b_{large j+n+1}, = &qquad, b_{large j+n} (1+b_{large j+n})\
= &, color{#c00}b(1+nb)(1+b+ncolor{#c00}{b^2)}\
equiv &, b(1+nb)(1+b) {rm by} color{#c00}bcolor{#c00}{b^2}equiv 0\
equiv &, b(1+(n!+!1)b)\
equiv &, b(1+b)^{large n+1}qquadqquadquad {bf QED}
end{align}qquadqquadqquad $
When $,b = 2!+!4iequiv 2pmod{!4}$ we can enlarge the modulus to $,4b^3$ since, as above
$quad begin{align}
bmod color{#c00}{4b^3}!: b_{j+n+1}
equiv &, b(1+(n!+!1)b) + color{#c00}2,{underbrace{n(1+nb/2}_{color{#c00}{rm even}})},color{#c00}{b^3}\[.2em]
end{align}qquadqquadqquad $
Here $,b_2 = 6,$ so we get $,b_{2+n}equiv 6 + 36npmod{!864},,$ just as you observed.
add a comment |
up vote
1
down vote
Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.
Notice $bmod 864!: a_n = 7! +! 36j Longrightarrow color{#0a0}{a_{n+1}},equiv, color{#0a0}{a_n}!+color{#c00}{36}, $ by
$underbrace{color{#0a0}{a_{n+1}!-!a_n} = (a_n!-!1)^2}_{Large a_{n+1} = a_n^2-a_n+1}! = (6!+!36j)^2! = 36+432,underbrace{j(1!+!3j)}_{large rm even}equiv color{#c00}{36}.,$
Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $, (1+b)^n = color{#0a0}{1+nb},pmod{!b^2}.,$ To make this clearer we examine the sequence $,b_n := a_n! - 1,,$ which satisfies $,b_{k+1} = b_k + b_k^2,, b_0 = 1.$
Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $,b_{k+1} = b_k(1+ b_k).,$ Then $$ b := b_{large k}, Rightarrow, b_{large k+n} equiv b(1+b)^nequiv b(color{#0a0}{1+nb}) pmod {!b^3}qquad $$
Proof $ $ By induction on $n$. Clear if $n=0.,$ Suppose for induction it is true for $n$. Then
$qquad begin{align}
bmod color{#c00}{b^3}!: b_{large j+n+1}, = &qquad, b_{large j+n} (1+b_{large j+n})\
= &, color{#c00}b(1+nb)(1+b+ncolor{#c00}{b^2)}\
equiv &, b(1+nb)(1+b) {rm by} color{#c00}bcolor{#c00}{b^2}equiv 0\
equiv &, b(1+(n!+!1)b)\
equiv &, b(1+b)^{large n+1}qquadqquadquad {bf QED}
end{align}qquadqquadqquad $
When $,b = 2!+!4iequiv 2pmod{!4}$ we can enlarge the modulus to $,4b^3$ since, as above
$quad begin{align}
bmod color{#c00}{4b^3}!: b_{j+n+1}
equiv &, b(1+(n!+!1)b) + color{#c00}2,{underbrace{n(1+nb/2}_{color{#c00}{rm even}})},color{#c00}{b^3}\[.2em]
end{align}qquadqquadqquad $
Here $,b_2 = 6,$ so we get $,b_{2+n}equiv 6 + 36npmod{!864},,$ just as you observed.
add a comment |
up vote
1
down vote
up vote
1
down vote
Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.
Notice $bmod 864!: a_n = 7! +! 36j Longrightarrow color{#0a0}{a_{n+1}},equiv, color{#0a0}{a_n}!+color{#c00}{36}, $ by
$underbrace{color{#0a0}{a_{n+1}!-!a_n} = (a_n!-!1)^2}_{Large a_{n+1} = a_n^2-a_n+1}! = (6!+!36j)^2! = 36+432,underbrace{j(1!+!3j)}_{large rm even}equiv color{#c00}{36}.,$
Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $, (1+b)^n = color{#0a0}{1+nb},pmod{!b^2}.,$ To make this clearer we examine the sequence $,b_n := a_n! - 1,,$ which satisfies $,b_{k+1} = b_k + b_k^2,, b_0 = 1.$
Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $,b_{k+1} = b_k(1+ b_k).,$ Then $$ b := b_{large k}, Rightarrow, b_{large k+n} equiv b(1+b)^nequiv b(color{#0a0}{1+nb}) pmod {!b^3}qquad $$
Proof $ $ By induction on $n$. Clear if $n=0.,$ Suppose for induction it is true for $n$. Then
$qquad begin{align}
bmod color{#c00}{b^3}!: b_{large j+n+1}, = &qquad, b_{large j+n} (1+b_{large j+n})\
= &, color{#c00}b(1+nb)(1+b+ncolor{#c00}{b^2)}\
equiv &, b(1+nb)(1+b) {rm by} color{#c00}bcolor{#c00}{b^2}equiv 0\
equiv &, b(1+(n!+!1)b)\
equiv &, b(1+b)^{large n+1}qquadqquadquad {bf QED}
end{align}qquadqquadqquad $
When $,b = 2!+!4iequiv 2pmod{!4}$ we can enlarge the modulus to $,4b^3$ since, as above
$quad begin{align}
bmod color{#c00}{4b^3}!: b_{j+n+1}
equiv &, b(1+(n!+!1)b) + color{#c00}2,{underbrace{n(1+nb/2}_{color{#c00}{rm even}})},color{#c00}{b^3}\[.2em]
end{align}qquadqquadqquad $
Here $,b_2 = 6,$ so we get $,b_{2+n}equiv 6 + 36npmod{!864},,$ just as you observed.
Below I give a simple direct proof, then I explain how it boils down to the Binomial Theorem.
Notice $bmod 864!: a_n = 7! +! 36j Longrightarrow color{#0a0}{a_{n+1}},equiv, color{#0a0}{a_n}!+color{#c00}{36}, $ by
$underbrace{color{#0a0}{a_{n+1}!-!a_n} = (a_n!-!1)^2}_{Large a_{n+1} = a_n^2-a_n+1}! = (6!+!36j)^2! = 36+432,underbrace{j(1!+!3j)}_{large rm even}equiv color{#c00}{36}.,$
Remark $ $ This is closely connected to the arithmetic progression that arises from the first two terms of the Binomial Theorem $, (1+b)^n = color{#0a0}{1+nb},pmod{!b^2}.,$ To make this clearer we examine the sequence $,b_n := a_n! - 1,,$ which satisfies $,b_{k+1} = b_k + b_k^2,, b_0 = 1.$
Lemma $ $ Suppose a sequence $b_k$ satisfies the recurrence $,b_{k+1} = b_k(1+ b_k).,$ Then $$ b := b_{large k}, Rightarrow, b_{large k+n} equiv b(1+b)^nequiv b(color{#0a0}{1+nb}) pmod {!b^3}qquad $$
Proof $ $ By induction on $n$. Clear if $n=0.,$ Suppose for induction it is true for $n$. Then
$qquad begin{align}
bmod color{#c00}{b^3}!: b_{large j+n+1}, = &qquad, b_{large j+n} (1+b_{large j+n})\
= &, color{#c00}b(1+nb)(1+b+ncolor{#c00}{b^2)}\
equiv &, b(1+nb)(1+b) {rm by} color{#c00}bcolor{#c00}{b^2}equiv 0\
equiv &, b(1+(n!+!1)b)\
equiv &, b(1+b)^{large n+1}qquadqquadquad {bf QED}
end{align}qquadqquadqquad $
When $,b = 2!+!4iequiv 2pmod{!4}$ we can enlarge the modulus to $,4b^3$ since, as above
$quad begin{align}
bmod color{#c00}{4b^3}!: b_{j+n+1}
equiv &, b(1+(n!+!1)b) + color{#c00}2,{underbrace{n(1+nb/2}_{color{#c00}{rm even}})},color{#c00}{b^3}\[.2em]
end{align}qquadqquadqquad $
Here $,b_2 = 6,$ so we get $,b_{2+n}equiv 6 + 36npmod{!864},,$ just as you observed.
edited Nov 18 at 0:13
Gerry Myerson
145k8147298
145k8147298
answered Nov 16 at 21:59
Bill Dubuque
207k29189624
207k29189624
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3001631%2fproof-that-sylvester-numbers-when-reduced-modulo-864-form-an-arithmetic-progr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Please see math.meta.stackexchange.com/questions/5020 Incidentally, have you an OEIS number for this sequence?
– Lord Shark the Unknown
Nov 16 at 21:00
It's easy to compute the Sylvester numbers modulo any small number, just use the recursive definition...$a_{n+1}=a_n^2-a_n+1$. $pmod {864}$ the sequence goes ${2,3,7,43,79,115,151,187,223,259,295,331,367,403,439,475,511,547,583,619,655,cdots }$ and so on.
– lulu
Nov 16 at 21:09
Sylvester's sequence at OEIS: oeis.org/A000058
– nickgard
Nov 16 at 21:15
I expanded my answer to show how it arises simply via the Binomial Theorem.
– Bill Dubuque
Nov 18 at 0:09
I don't see a question here.
– Gerry Myerson
Nov 18 at 0:11