Simple recursive calculations of Fibonacci numbers

In this article I proved that for any \(n, m > 2\), the following holds true for Fibonacci numbers \(F_n\):

\[ F_{n + m} = F_mF_{n+1} + F_{m-1}F_n \]

Now we can easily write a recursive function to calculate an arbitrarily large Fibonacci number based on knowing the first few numbers:

fibonacci <- function(x) {
  f <- c(1, 1, 2, 3, 5)
  if (x <= 5) {
    f[x]
  } else {
    n <- ceiling(x/2)
    m <- floor(x/2)
    fibonacci(m)*fibonacci(n+1) + fibonacci(m-1)*fibonacci(n)
  }
}

Let’s test it, doing our best to display very large numbers in R:

library(gmp)
fibonacci(30)

## [1] 832040

as.bigz(fibonacci(1000))

## Big Integer ('bigz') :
## [1] 43466557686937454881639861284285048836044564808501085299792936936934507578446811952241727283693776165701110466238201810459653426841499747856972973922645842460198740218733277412586280377875508003628944833118208

as.bigz(fibonacci(10000))

## Big Integer ('bigz') :
## [1] 173766203193809456599982445949435627061939786100117250547173286503262376022458008465094333630120854338003194362163007597987225472483598640843335685441710193966274131338557192586399006789292714554767500194796127964596906605976605873665859580600161998556511368530960400907199253450604168622770350228527124626728538626805418833470107651091641919900725415994689920112219170907023561354484047025713734651608777544579846111001059482132180956689444108315785401642188044178788629853592228467331730519810763559577944882016286493908631503101121166109571682295769470379514531105239965209245314082665518579335511291525230373316486697786532335206274149240813489201828773854353041855598709390675430960381072270432383913542702130202430186637321862331068861776780211082856984506050024895394320139435868484643843368002496089956046419964019877586845530207748994394501505588146979082629871366088121763790555364513243984244004147636040219136443410377798011608722717131323621700159335786445601947601694025107888293017058178562647175461026384343438874861406516767158373279032321096262126551620255666605185789463207944391905756886829667520553014724372245300878786091700563444079107099009003380230356461989260377273986023281444076082783406824471703499844642915587790146384758051663547775336021829171033411043796977042190519657861762804226147480755555085278062866268677842432851421790544407006581148631979148571299417963950579210719961422405768071335213324842709316205032078384168750091017964584060285240107161561019930505687950233196051962261970932008838279760834318101044311710769457048672103958655016388894770892065267451228938951370237422841366052736174160431593023473217066764172949768821843606479073866252864377064398085101223216558344281956767163876579889759124956035672317578122141070933058555310274598884089982879647974020264495921703064439532898207943134374576254840272047075633856749514044298135927611328433323640657533550512376900773273703275329924651465759145114579174356770593439987135755889403613364529029604049868233807295134382284730745937309910703657676103447124097631074153287120040247837143656624045055614076111832245239612708339272798262887437416818440064925049838443370805645609424314780108030016683461562597569371539974003402697903023830108053034645133078208043917492087248958344081026378788915528519967248989338592027124423914083391771884524464968645052058218151010508471258285907685355807229880747677634789376

We can also test that the rule of the Fibonacci sequence hold for very large \(n\):

fibonacci(1000) + fibonacci(1001) == fibonacci(1002)

## [1] TRUE

fibonacci(10000) + fibonacci(10001) == fibonacci(10002)

## [1] TRUE