Showing that the tribonacci sequence has relatively prime terms Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Prove that any two consecutive terms of the Fibonacci sequence are relatively primeInvent a combinatorial interpretation for the ''Tribonacci numbers''Proofs by strong inductionShow that the greatest common divisor of any two terms in recursive sequence $T_n+1 = T_n^2 - T_n + 1$ is 1.Let t(n) be the number of strings of n letters that can be produced by concatenating copies of the string “a”, “bc”, “cb” find t(3) and t(4)$gcd(f_k, f_k+3)$, where $f_k$ is the k'th Fibonacci numberStrengthening the Sylvester-Schur TheoremThere is a conjecture according to which only five Fibonacci numbers are also triangular numbers.How to change the base cases of a tribonacci sequence solved by matrix exponentationProving That Consecutive Fibonacci Numbers are Relatively Prime
What does the "x" in "x86" represent?
How do I find out the mythology and history of my Fortress?
Would "destroying" Wurmcoil Engine prevent its tokens from being created?
Do jazz musicians improvise on the parent scale in addition to the chord-scales?
Significance of Cersei's obsession with elephants?
Can an alien society believe that their star system is the universe?
Is there any way for the UK Prime Minister to make a motion directly dependent on Government confidence?
What does "lightly crushed" mean for cardamon pods?
Irreducible of finite Krull dimension implies quasi-compact?
How would a mousetrap for use in space work?
Denied boarding although I have proper visa and documentation. To whom should I make a complaint?
How to compare two different files line by line in unix?
2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?
What's the meaning of "fortified infraction restraint"?
Circuit to "zoom in" on mV fluctuations of a DC signal?
What do you call the main part of a joke?
What does this Jacques Hadamard quote mean?
How do I make this wiring inside cabinet safer? (Pic)
8 Prisoners wearing hats
For a new assistant professor in CS, how to build/manage a publication pipeline
When a candle burns, why does the top of wick glow if bottom of flame is hottest?
How does the math work when buying airline miles?
Why do we bend a book to keep it straight?
Do I really need to have a message in a novel to appeal to readers?
Showing that the tribonacci sequence has relatively prime terms
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Prove that any two consecutive terms of the Fibonacci sequence are relatively primeInvent a combinatorial interpretation for the ''Tribonacci numbers''Proofs by strong inductionShow that the greatest common divisor of any two terms in recursive sequence $T_n+1 = T_n^2 - T_n + 1$ is 1.Let t(n) be the number of strings of n letters that can be produced by concatenating copies of the string “a”, “bc”, “cb” find t(3) and t(4)$gcd(f_k, f_k+3)$, where $f_k$ is the k'th Fibonacci numberStrengthening the Sylvester-Schur TheoremThere is a conjecture according to which only five Fibonacci numbers are also triangular numbers.How to change the base cases of a tribonacci sequence solved by matrix exponentationProving That Consecutive Fibonacci Numbers are Relatively Prime
$begingroup$
Let $f_k$ denote the Fibonacci numbers. It turns out that $gcd(f_k,f_k+1)=1$ for all $kge 1$ and I understand this proof. If one defines the tribonacci numbers by $t_1=t_2=t_3=1$ and $t_k+3=t_k+2+t_k+1+t_k$, can one similarly prove that $gcd(t_k,t_k+1),t_k+2)=1$ for all $k$?
elementary-number-theory recurrence-relations fibonacci-numbers
asked Mar 27 at 3:39
SamSam
1198
$endgroup$
add a comment |
$begingroup$
Let $f_k$ denote the Fibonacci numbers. It turns out that $gcd(f_k,f_k+1)=1$ for all $kge 1$ and I understand this proof. If one defines the tribonacci numbers by $t_1=t_2=t_3=1$ and $t_k+3=t_k+2+t_k+1+t_k$, can one similarly prove that $gcd(t_k,t_k+1),t_k+2)=1$ for all $k$?
elementary-number-theory recurrence-relations fibonacci-numbers
asked Mar 27 at 3:39
SamSam
1198
$endgroup$
1
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48
add a comment |
$begingroup$
Let $f_k$ denote the Fibonacci numbers. It turns out that $gcd(f_k,f_k+1)=1$ for all $kge 1$ and I understand this proof. If one defines the tribonacci numbers by $t_1=t_2=t_3=1$ and $t_k+3=t_k+2+t_k+1+t_k$, can one similarly prove that $gcd(t_k,t_k+1),t_k+2)=1$ for all $k$?
elementary-number-theory recurrence-relations fibonacci-numbers
asked Mar 27 at 3:39
SamSam
1198
$endgroup$
Let $f_k$ denote the Fibonacci numbers. It turns out that $gcd(f_k,f_k+1)=1$ for all $kge 1$ and I understand this proof. If one defines the tribonacci numbers by $t_1=t_2=t_3=1$ and $t_k+3=t_k+2+t_k+1+t_k$, can one similarly prove that $gcd(t_k,t_k+1),t_k+2)=1$ for all $k$?
elementary-number-theory recurrence-relations fibonacci-numbers
elementary-number-theory recurrence-relations fibonacci-numbers
asked Mar 27 at 3:39
SamSam
1198
asked Mar 27 at 3:39
SamSam
1198
edited Mar 27 at 13:46
Sam
asked Mar 27 at 3:39
SamSam
1198
asked Mar 27 at 3:39
SamSam
1198
asked Mar 27 at 3:39
SamSam
1198
1198
1
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48
add a comment |
1
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48
1
1
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As darij grinberg says in the comments, the property does hold for the tribonacci numbers as you define them.
To see this, we show by induction that if at any point in the sequence, $gcd(t_k,t_k+1,t_k+2)=1$, then it will always be true that $gcd(t_k,t_k+1,t_k+2)=1$ for all $k$. Since $gcd(1,1,1)=1$, the base case is satisfied for the tribonacci numbers.
Suppose $gcd(t_k-1,t_k,t_k+1)=1$. Then $gcd(t_k,t_k+1,t_k+2)=gcd(t_k,t_k+1,t_k-1+t_k+t_k+1)$. If $p$ is any number that divides $t_k$, $t_k+1$, and $t_k-1+t_k+t_k+1$, then it also divides $(t_k-1+t_k+t_k+1) - t_k - t_k+1 = t_k-1$. Then $p$ divides $gcd(t_k-1,t_k,t_k+1)=1$, so $gcd(t_k,t_k+1,t_k+2)=1$.
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
$endgroup$
add a comment |
$begingroup$
We have
$$
beginpmatrixt_n+3 \ t_n+2 \ t_n+1 endpmatrix
=beginpmatrix1&1&1\1&0&0\0&1&0endpmatrix
beginpmatrixt_n+2 \ t_n+1 \ t_n endpmatrix
$$
The matrix has determinant $1$ and so is invertible over the integers.
Therefore, the common divisors of $t_n+3, t_n+2, t_n+1$ are exactly the same as the common divisors of $t_n+2, t_n+1, t_n$.
answered Mar 27 at 14:34
lhflhf
168k11172405
$endgroup$
add a comment |
Your Answer
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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%2f3164070%2fshowing-that-the-tribonacci-sequence-has-relatively-prime-terms%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As darij grinberg says in the comments, the property does hold for the tribonacci numbers as you define them.
To see this, we show by induction that if at any point in the sequence, $gcd(t_k,t_k+1,t_k+2)=1$, then it will always be true that $gcd(t_k,t_k+1,t_k+2)=1$ for all $k$. Since $gcd(1,1,1)=1$, the base case is satisfied for the tribonacci numbers.
Suppose $gcd(t_k-1,t_k,t_k+1)=1$. Then $gcd(t_k,t_k+1,t_k+2)=gcd(t_k,t_k+1,t_k-1+t_k+t_k+1)$. If $p$ is any number that divides $t_k$, $t_k+1$, and $t_k-1+t_k+t_k+1$, then it also divides $(t_k-1+t_k+t_k+1) - t_k - t_k+1 = t_k-1$. Then $p$ divides $gcd(t_k-1,t_k,t_k+1)=1$, so $gcd(t_k,t_k+1,t_k+2)=1$.
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
$endgroup$
add a comment |
$begingroup$
As darij grinberg says in the comments, the property does hold for the tribonacci numbers as you define them.
To see this, we show by induction that if at any point in the sequence, $gcd(t_k,t_k+1,t_k+2)=1$, then it will always be true that $gcd(t_k,t_k+1,t_k+2)=1$ for all $k$. Since $gcd(1,1,1)=1$, the base case is satisfied for the tribonacci numbers.
Suppose $gcd(t_k-1,t_k,t_k+1)=1$. Then $gcd(t_k,t_k+1,t_k+2)=gcd(t_k,t_k+1,t_k-1+t_k+t_k+1)$. If $p$ is any number that divides $t_k$, $t_k+1$, and $t_k-1+t_k+t_k+1$, then it also divides $(t_k-1+t_k+t_k+1) - t_k - t_k+1 = t_k-1$. Then $p$ divides $gcd(t_k-1,t_k,t_k+1)=1$, so $gcd(t_k,t_k+1,t_k+2)=1$.
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
$endgroup$
add a comment |
$begingroup$
As darij grinberg says in the comments, the property does hold for the tribonacci numbers as you define them.
To see this, we show by induction that if at any point in the sequence, $gcd(t_k,t_k+1,t_k+2)=1$, then it will always be true that $gcd(t_k,t_k+1,t_k+2)=1$ for all $k$. Since $gcd(1,1,1)=1$, the base case is satisfied for the tribonacci numbers.
Suppose $gcd(t_k-1,t_k,t_k+1)=1$. Then $gcd(t_k,t_k+1,t_k+2)=gcd(t_k,t_k+1,t_k-1+t_k+t_k+1)$. If $p$ is any number that divides $t_k$, $t_k+1$, and $t_k-1+t_k+t_k+1$, then it also divides $(t_k-1+t_k+t_k+1) - t_k - t_k+1 = t_k-1$. Then $p$ divides $gcd(t_k-1,t_k,t_k+1)=1$, so $gcd(t_k,t_k+1,t_k+2)=1$.
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
$endgroup$
As darij grinberg says in the comments, the property does hold for the tribonacci numbers as you define them.
To see this, we show by induction that if at any point in the sequence, $gcd(t_k,t_k+1,t_k+2)=1$, then it will always be true that $gcd(t_k,t_k+1,t_k+2)=1$ for all $k$. Since $gcd(1,1,1)=1$, the base case is satisfied for the tribonacci numbers.
Suppose $gcd(t_k-1,t_k,t_k+1)=1$. Then $gcd(t_k,t_k+1,t_k+2)=gcd(t_k,t_k+1,t_k-1+t_k+t_k+1)$. If $p$ is any number that divides $t_k$, $t_k+1$, and $t_k-1+t_k+t_k+1$, then it also divides $(t_k-1+t_k+t_k+1) - t_k - t_k+1 = t_k-1$. Then $p$ divides $gcd(t_k-1,t_k,t_k+1)=1$, so $gcd(t_k,t_k+1,t_k+2)=1$.
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
answered Mar 27 at 4:01
Ethan MacBroughEthan MacBrough
1,271617
1,271617
add a comment |
add a comment |
$begingroup$
We have
$$
beginpmatrixt_n+3 \ t_n+2 \ t_n+1 endpmatrix
=beginpmatrix1&1&1\1&0&0\0&1&0endpmatrix
beginpmatrixt_n+2 \ t_n+1 \ t_n endpmatrix
$$
The matrix has determinant $1$ and so is invertible over the integers.
Therefore, the common divisors of $t_n+3, t_n+2, t_n+1$ are exactly the same as the common divisors of $t_n+2, t_n+1, t_n$.
answered Mar 27 at 14:34
lhflhf
168k11172405
$endgroup$
add a comment |
$begingroup$
We have
$$
beginpmatrixt_n+3 \ t_n+2 \ t_n+1 endpmatrix
=beginpmatrix1&1&1\1&0&0\0&1&0endpmatrix
beginpmatrixt_n+2 \ t_n+1 \ t_n endpmatrix
$$
The matrix has determinant $1$ and so is invertible over the integers.
Therefore, the common divisors of $t_n+3, t_n+2, t_n+1$ are exactly the same as the common divisors of $t_n+2, t_n+1, t_n$.
answered Mar 27 at 14:34
lhflhf
168k11172405
$endgroup$
add a comment |
$begingroup$
We have
$$
beginpmatrixt_n+3 \ t_n+2 \ t_n+1 endpmatrix
=beginpmatrix1&1&1\1&0&0\0&1&0endpmatrix
beginpmatrixt_n+2 \ t_n+1 \ t_n endpmatrix
$$
The matrix has determinant $1$ and so is invertible over the integers.
Therefore, the common divisors of $t_n+3, t_n+2, t_n+1$ are exactly the same as the common divisors of $t_n+2, t_n+1, t_n$.
answered Mar 27 at 14:34
lhflhf
168k11172405
$endgroup$
We have
$$
beginpmatrixt_n+3 \ t_n+2 \ t_n+1 endpmatrix
=beginpmatrix1&1&1\1&0&0\0&1&0endpmatrix
beginpmatrixt_n+2 \ t_n+1 \ t_n endpmatrix
$$
The matrix has determinant $1$ and so is invertible over the integers.
Therefore, the common divisors of $t_n+3, t_n+2, t_n+1$ are exactly the same as the common divisors of $t_n+2, t_n+1, t_n$.
answered Mar 27 at 14:34
lhflhf
168k11172405
answered Mar 27 at 14:34
lhflhf
168k11172405
answered Mar 27 at 14:34
lhflhf
168k11172405
answered Mar 27 at 14:34
lhflhf
168k11172405
168k11172405
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.
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%2f3164070%2fshowing-that-the-tribonacci-sequence-has-relatively-prime-terms%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
1
$begingroup$
Check your $k=4$ calculations again; I think the gcd is $1$ for every $k$.
$endgroup$
– darij grinberg
Mar 27 at 3:43
$begingroup$
You're absolutely correct. For some reason I misremembered the gcd of three terms being 1 meaning that the gcd of each pair of terms was 1. I've edited the problem appropriately.
$endgroup$
– Sam
Mar 27 at 13:48