## It's All About Powers of 10

Here is an interesting problem from the 29th Annual Virginia Tech Regional Mathematics Contest: find the third digit after the decimal point of the following number

 (2 + √5)100 ((1 + √2)100 + (1 + √2)-100).

The problem is interesting in that the exact result can be found by estimation.

Call the number at hand N. N is a product of two factors. The second one,

 (1 + √2)100 + (1 + √2)-100

is an integer. To see that first observe that (1 + 2)-1 = (2 - 1). Further, by the binomial theorem, for any even power 2n, the expression

 (√2 + 1)2n + (√2 - 1)2n

is an integer because in the expansion of the two binomials the terms with odd powers of 2 will have different signs and, therefore, will cancel out.

In the same vein, the expression

 ((√5 + 2)2n + (√5 - 2)2n) ((√2 + 1)2n + (√2 - 1)2n)

is an integer, for any positive integer n. It follows that the two numbers

 N(n) = (√5 + 2)2n ((√2 + 1)2n + (√2 - 1)2n) and M(n) = (√5 - 2)2n ((√2 + 1)2n + (√2 - 1)2n)

add up to an integer so that their decimal parts are complementary, i.e., add up to 1.

Now, it so happens that finding the decimal digits of M(n) is much easier than finding the decimal digits of N(n). This is because M(n) < 1 and, furthermore, has a few zeros right after the decimal point whose number grows with n. For n = 50, as in the problem at hand, there are 25 zeros after the point. This means that N = N(50) has as many 9's after the point. In particular, its third digit is also 9.

To solve the problem we have to estimate M(50). We'll use another identity to get a very rude but fast mental estimate

 √5 - 2 = (√5 + 2)-1.

Here goes the estimate:

 M(50) < (√5 + 2)-100 2 (((√2 + 1)100) < 4-100 2 (5/2)100 = 2 (5/8)100 < 2 (.7)100 < 2 (.5)50 = 2 (.25)25 < 2 (.0625)12 = 10-12 2 (.625)12 < 10-12,

a number with 11 0s after the point. Which is more than enough to claim 0 for the third digit. A more accurate estimate with a calculator gives

 M(50) < 3.82·10-25.

The standard UNIX calculator bc, with the precision of 1000 decimal digits gave the following:

 .0000000000000000000000003813084756492757038435970667033249787818837 77773402278685731345374788100039480576315819907918085676803021954244 74841332406865726192265588360611050676923510428046288103761135460645 50428768856685063457896358622025725426261515900056533845295227535252 93205586627913041446047425245333857708488850679243674256351347901435 66830219677054551266610355818107558725790265678607876718493816614352 23840229894711391896841199903988776274930582312396326518612416948934 13995263781761287430084457414973769096695200921487332968400598206548 71674321599774345287600512918360983157386792069829034310329757778403 14697907680202879759525995372704025202597536854850895528284720190010 43997104627716228979599560491891544256284517476871766858286204467163 34948318843358623790220812033340318054683845668036474168838478033432 40053251308900254939423059923487852492077443131647545675595497966552 85087761526257607592788312756316597036348867940950977200762216898101 9809954995385479261942702746357095042592317611233

for M(50) and

 94158733601034420664808450657998303298219601745567527892456021922994 873597395955752869490271254871747.9999999999999999999999996186915243 50724296156402933296675021218116222226597721314268654625211899960519 42368418009208191432319697804575525158667593134273807734411639388949 32307648957195371189623886453935449571231143314936542103641377974274 57373848409994346615470477246474706794413372086958553952574754666142 29151114932075632574364865209856433169780322945448733389644181892441 27420973432139212328150618338564776159770105288608103158800096011223 72506941768760367348138758305106586004736218238712569915542585026230 90330479907851266703159940179345128325678400225654712399487081639016 84261320793017096568967024222159685302092319797120240474004627295974 79740246314514910447171527980998956002895372283771020400439508108455 74371548252312823314171379553283665051681156641376209779187966659681 94531615433196352583116152196656759946748691099745060576940076512147 50792255686835245432440450203344714912238473742309557459413566080518 10248051261191700248203749909991013069100325677059884894391440358506 72718850849642

for N(50). And here is another table that juxstaposes the decimal digits of the two numbers (884 of them):

 00000000000000000000000038130847564927570384359706670332497878188377 99999999999999999999999961869152435072429615640293329667502121811622 77734022786857313453747881000394805763158199079180856768030219542447 22265977213142686546252118999605194236841800920819143231969780457552 48413324068657261922655883606110506769235104280462881037611354606455 51586675931342738077344116393889493230764895719537118962388645393544 04287688566850634578963586220257254262615159000565338452952275352529 95712311433149365421036413779742745737384840999434661547047724647470 32055866279130414460474252453338577084888506792436742563513479014356 67944133720869585539525747546661422915111493207563257436486520985643 68302196770545512666103558181075587257902656786078767184938166143522 31697803229454487333896441818924412742097343213921232815061833856477 38402298947113918968411999039887762749305823123963265186124169489341 61597701052886081031588000960112237250694176876036734813875830510658 39952637817612874300844574149737690966952009214873329684005982065487 60047362182387125699155425850262309033047990785126670315994017934512 16743215997743452876005129183609831573867920698290343103297577784031 83256784002256547123994870816390168426132079301709656896702422215968 46979076802028797595259953727040252025975368548508955282847201900104 53020923197971202404740046272959747974024631451491044717152798099895 39971046277162289795995604918915442562845174768717668582862044671633 60028953722837710204004395081084557437154825231282331417137955328366 49483188433586237902208120333403180546838456680364741688384780334324 50516811566413762097791879666596819453161543319635258311615219665675 00532513089002549394230599234878524920774431316475456755954979665528 99467486910997450605769400765121475079225568683524543244045020334471