5
$\begingroup$

This looks like a difficult problem:

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

(it is from a competition training; trainer suggests using pigeonhole principle)

$\endgroup$
2
  • 2
    $\begingroup$ Then ignore the trainer. Its advice can be useful if you get stuck after you've gotten somewhere into the problem, but it's worthless for actually starting the problem. $\endgroup$ – user14972 Sep 21 '14 at 22:42
  • 1
    $\begingroup$ Hint: $100000001=1\, 0000^2+1$. This is no coincidence. $\endgroup$ – Yves Daoust May 7 '15 at 7:52
14
$\begingroup$

Consider Fibonacci numbers $\mod 10000$. The sequence begins: $F_0=0, 1, 1, \ldots$ and continues until $F_{100000001}$. Consider the set of $100000001$ ordered pairs $(F_n, F_{n+1})$. By the pigeonhole principle, at least one of these ordered pairs occurs twice in the sequence.

Now note that the entire sequence of Fibonacci numbers $\mod 10000$ are uniquely determined by any two consecutive values, as the sequence can be constructed both forwards and backwards. ($F_n\equiv F_{n+2}-F_{n+1} \mod 10000$).

So if the ordered pair $(F_n, F_{n+1})$ occurs at both $n=m$ and $n=m+t$ for $m,t \in \mathbb{N}$, then the sequence is recurrent ($F_n \equiv F_{n+t} \mod 10000$ for all $n$).

Hence the ordered pair $(F_n=0, F_{n+1}=1)$ must also occur at both $n=0$ and $n=t$. And since $m+t$ is among the first 100000001 Fibonacci numbers, then $t$ must also be among them.

$\endgroup$
2
  • $\begingroup$ Excellent, thanks! It looks now not that difficult at all. $\endgroup$ – VividD Sep 21 '14 at 23:03
  • $\begingroup$ There's an important detail this leaves out; you show that the sequence is eventually cyclic - that is $F_n\equiv F_{n+t}\mod 10000$ for all large enough $n$ - but you then use that it holds for $n=1$. You need to notice that the map $(a,b)\mapsto (b,a+b)$ (which transitions $(F_{n-1},F_n)$ to $(F_n,F_{n+1})$) is a bijection (working mod 10000) in order to conclude that it is periodic. Otherwise, repeated applications of that map might enter a cycle, but one which does not include $(0,1)$. (e.g. like how the map $f(x)=max(x-1,0)$ acts - eventually cyclic, but not a bijection) $\endgroup$ – Milo Brandt Apr 14 '15 at 23:30
4
$\begingroup$

This is slightly irrelevant to what you are looking for, but I'm sure you'll be happy to know that for $n = 7500$,

f(n) = 11423965231520587047220488928656904198487186633317560797959030595738263643588305263964321080516991429937628886229555340146644442744473185460778302934743807002248109695741208782411159189994651520930091202035101269350523609417276542209682261168150544790025062794209091503702088574338650460569295592498666443239807989522593072562158640947468656887645879356201301594841872491497556389555817277508349058330498007583814270123329724353233156029127910968370052734811192660492733375394472692191584489489590970254440914222778382439339334175624660291588778456250479185237898309112318829984358216337347549014336517486496643224502773380042071174360597192343056318489287038447004730922073980870072990706067508624038407888471294048912294153491398930715643640170172837379127969101176561450586945715460276780809807889664272818316865711724985646554559305334340318994612185260719042008960311269000122672589731283419608098303367260382379660402261886574952211783683104453334281684425994447306306414660032519055079504313562694958935754118796157632978970220780288168992181699708922971417067735144929461193639081445200786881549331150381216073705417531166786634690469206418611524663013854198045284806720735273715046888704916821855277543026346215355286395854263168251068150374988851620501196943905031285049077628443804052134507022504682483293396215268186620124762379744668092166035314553541731537245946256422861852573006230492322259630342294350827184840607509969289328320360093204783447860955806396350723341261564285649453007949089154165288839814442677339344794691881510389855765582716774490000,

so there is at least one!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.