Show congruence with Fibonacci number

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite












I want to show that for each $n geq 1$ it holds that:



$$2^n-1 F_n equiv n pmod5$$



where $F_n$ is the $n$-th Fibonacci number.



Could you give a hint how we can show this?



The sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:



$$F_n=F_n-1+F_n-2 \ F_1=1, F_2=1.$$



Right? Do we use the definion in order to get to the desired result?






number-theory fibonacci-numbers







share|cite|improve this question

















  • 2




    "Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
    – Arthur
    32 mins ago














up vote
1
down vote

favorite












I want to show that for each $n geq 1$ it holds that:



$$2^n-1 F_n equiv n pmod5$$



where $F_n$ is the $n$-th Fibonacci number.



Could you give a hint how we can show this?



The sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:



$$F_n=F_n-1+F_n-2 \ F_1=1, F_2=1.$$



Right? Do we use the definion in order to get to the desired result?






number-theory fibonacci-numbers







share|cite|improve this question

















  • 2




    "Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
    – Arthur
    32 mins ago












up vote
1
down vote

favorite









up vote
1
down vote

favorite











I want to show that for each $n geq 1$ it holds that:



$$2^n-1 F_n equiv n pmod5$$



where $F_n$ is the $n$-th Fibonacci number.



Could you give a hint how we can show this?



The sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:



$$F_n=F_n-1+F_n-2 \ F_1=1, F_2=1.$$



Right? Do we use the definion in order to get to the desired result?






number-theory fibonacci-numbers







share|cite|improve this question













I want to show that for each $n geq 1$ it holds that:



$$2^n-1 F_n equiv n pmod5$$



where $F_n$ is the $n$-th Fibonacci number.



Could you give a hint how we can show this?



The sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:



$$F_n=F_n-1+F_n-2 \ F_1=1, F_2=1.$$



Right? Do we use the definion in order to get to the desired result?






number-theory fibonacci-numbers




number-theory fibonacci-numbers






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 42 mins ago









Evinda

619413




619413







  • 2




    "Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
    – Arthur
    32 mins ago












  • 2




    "Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
    – Arthur
    32 mins ago







2




2




"Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
– Arthur
32 mins ago




"Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly.
– Arthur
32 mins ago










2 Answers
2






active

oldest

votes

















up vote
1
down vote



accepted










$$2^n-1F_n=2^n-1(F_n-1+F_n-2)=2(2^n-2F_n-1)+4(2^n-3F_n-2)
\equiv 2(n-1)+4(n-2)
equiv 6n-10equiv nmod5.$$



Also,



$$2^1-1F_1=1equiv 1$$ and



$$2^2-1F_2=2equiv 2.$$






share|cite|improve this answer




















  • Thanks a lot!!! :)
    – Evinda
    12 mins ago

















up vote
3
down vote













By induction over $n$, the base cases $n=1,2$ are trivial.



$$beginalign 2^k F_k+1 &= 2^k(F_k+F_k-1)\
&= 2^kF_k+2^kF_k-1 \
&equiv 2k+4(k-1) pmod5\
&equiv k+1 pmod5 endalign$$






share|cite|improve this answer




















  • @Additldent Thank you :-)
    – Evinda
    12 mins ago










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


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2974443%2fshow-congruence-with-fibonacci-number%23new-answer', 'question_page');

);

Post as a guest

















2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote



accepted










$$2^n-1F_n=2^n-1(F_n-1+F_n-2)=2(2^n-2F_n-1)+4(2^n-3F_n-2)
\equiv 2(n-1)+4(n-2)
equiv 6n-10equiv nmod5.$$



Also,



$$2^1-1F_1=1equiv 1$$ and



$$2^2-1F_2=2equiv 2.$$






share|cite|improve this answer




















  • Thanks a lot!!! :)
    – Evinda
    12 mins ago














up vote
1
down vote



accepted










$$2^n-1F_n=2^n-1(F_n-1+F_n-2)=2(2^n-2F_n-1)+4(2^n-3F_n-2)
\equiv 2(n-1)+4(n-2)
equiv 6n-10equiv nmod5.$$



Also,



$$2^1-1F_1=1equiv 1$$ and



$$2^2-1F_2=2equiv 2.$$






share|cite|improve this answer




















  • Thanks a lot!!! :)
    – Evinda
    12 mins ago












up vote
1
down vote



accepted







up vote
1
down vote



accepted






$$2^n-1F_n=2^n-1(F_n-1+F_n-2)=2(2^n-2F_n-1)+4(2^n-3F_n-2)
\equiv 2(n-1)+4(n-2)
equiv 6n-10equiv nmod5.$$



Also,



$$2^1-1F_1=1equiv 1$$ and



$$2^2-1F_2=2equiv 2.$$






share|cite|improve this answer












$$2^n-1F_n=2^n-1(F_n-1+F_n-2)=2(2^n-2F_n-1)+4(2^n-3F_n-2)
\equiv 2(n-1)+4(n-2)
equiv 6n-10equiv nmod5.$$



Also,



$$2^1-1F_1=1equiv 1$$ and



$$2^2-1F_2=2equiv 2.$$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 25 mins ago









Yves Daoust

119k667215




119k667215











  • Thanks a lot!!! :)
    – Evinda
    12 mins ago
















  • Thanks a lot!!! :)
    – Evinda
    12 mins ago















Thanks a lot!!! :)
– Evinda
12 mins ago




Thanks a lot!!! :)
– Evinda
12 mins ago










up vote
3
down vote













By induction over $n$, the base cases $n=1,2$ are trivial.



$$beginalign 2^k F_k+1 &= 2^k(F_k+F_k-1)\
&= 2^kF_k+2^kF_k-1 \
&equiv 2k+4(k-1) pmod5\
&equiv k+1 pmod5 endalign$$






share|cite|improve this answer




















  • @Additldent Thank you :-)
    – Evinda
    12 mins ago














up vote
3
down vote













By induction over $n$, the base cases $n=1,2$ are trivial.



$$beginalign 2^k F_k+1 &= 2^k(F_k+F_k-1)\
&= 2^kF_k+2^kF_k-1 \
&equiv 2k+4(k-1) pmod5\
&equiv k+1 pmod5 endalign$$






share|cite|improve this answer




















  • @Additldent Thank you :-)
    – Evinda
    12 mins ago












up vote
3
down vote










up vote
3
down vote









By induction over $n$, the base cases $n=1,2$ are trivial.



$$beginalign 2^k F_k+1 &= 2^k(F_k+F_k-1)\
&= 2^kF_k+2^kF_k-1 \
&equiv 2k+4(k-1) pmod5\
&equiv k+1 pmod5 endalign$$






share|cite|improve this answer












By induction over $n$, the base cases $n=1,2$ are trivial.



$$beginalign 2^k F_k+1 &= 2^k(F_k+F_k-1)\
&= 2^kF_k+2^kF_k-1 \
&equiv 2k+4(k-1) pmod5\
&equiv k+1 pmod5 endalign$$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 37 mins ago









AdditIdent

35119




35119











  • @Additldent Thank you :-)
    – Evinda
    12 mins ago
















  • @Additldent Thank you :-)
    – Evinda
    12 mins ago















@Additldent Thank you :-)
– Evinda
12 mins ago




@Additldent Thank you :-)
– Evinda
12 mins ago

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2974443%2fshow-congruence-with-fibonacci-number%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
Read more

List of Gilmore Girls characters

Image
The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
Read more

Confectionery

Image
Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of ...
Read more