21
$\begingroup$

I have to compare the following two numbers:

$$2013! \text{ and } 1007^{2013}$$

where $n! = 1 \times 2 \times \cdots \times (n-1) \times n$.

I tried in different ways to group the $1 \times 2 \times \cdots \times 2012 \times 2013$ to obtain some kind of association with the $1007$ from $1007^{2013}$ but no luck.

Is there any standard approach for this kind of problem?

$\endgroup$
1
  • 1
    $\begingroup$ Do you know the AM/GM intequality - that is, the geometric mean of a set of numbers is always less than or equal to the arithmetic mean? $\endgroup$ Mar 8, 2013 at 15:43

8 Answers 8

49
+50
$\begingroup$

$1\times 2\times\ldots\times 2012\times 2013$

$=(1007-1006)\times(1007-1005)\times\ldots\times (1007+1005)\times(1007+1006)$

$=(1007^2-1006^2)\times (1007^2-1005^2)\times\ldots\times (1007^2-1^2)\times 1007$

$<(1007^2)^{1006}\times 1007$

$=1007^{2013}$

$\endgroup$
3
  • 3
    $\begingroup$ Thank you! All answers were helpful but I chose this one because it is really clear and in this case I needed a solution which does not require advanced mathematical knowledge. Thanks again! $\endgroup$
    – Ionut
    Mar 8, 2013 at 16:02
  • 10
    $\begingroup$ In general, the AM-GM says that $n!\le\left(\frac{n+1}{2}\right)^n$ $\endgroup$
    – robjohn
    Mar 8, 2013 at 16:17
  • 1
    $\begingroup$ @robjohn that's good to know. Thank you! $\endgroup$
    – Ionut
    Mar 8, 2013 at 17:49
26
$\begingroup$

You can just take the inequality between the arithmetic and geometric means:

$$\sqrt[n]{a_1a_2\dots a_n}\leq \frac{a_1+a_2\dots+a_n}{n}$$

with $a_i=i$ and $n=2013$. Then $\sqrt[2013]{2013!} \leq 1007$.

$\endgroup$
2
  • $\begingroup$ I just noticed that this is the justification for my comment to Jacob Black's answer :-) $\endgroup$
    – robjohn
    Mar 8, 2013 at 20:40
  • $\begingroup$ Yeah, I originally had the same asnwer as most of the rest, but then I saw the AM/GM relationship made it all crystal clear. Most of the "direct" proofs using $(1007-i)(1007+i)<1007^2$ are just using the basic case of AM/GM with $n=2$. :) @robjohn $\endgroup$ Mar 8, 2013 at 20:54
17
$\begingroup$

Use Stirling’s approximation for the factorial:

$$n!\sim\sqrt{2\pi n}\left(\frac{n}e\right)^n\;,$$

so $$2013!\approx 112.46356(740.54132)^{2013}<1007^{2013}\;.$$

For a less computational approach, look at their ratio:

$$\begin{align*}\frac{2013!}{{1007}^{2013}}&=\frac{2013\cdot2012\cdot\ldots\cdot2\cdot1}{1007\cdot1007\cdot\ldots\cdot1007\cdot1007}\\\\ &=\underbrace{\frac{2013}{1007}\cdot\frac{2012}{1007}\cdot\frac{2011}{1007}\cdot\ldots\cdot\frac{1008}{1007}}_{1006\text{ factors}}\cdot\frac{1007}{1007}\cdot\underbrace{\frac{1006}{1007}\ldots\cdot\frac2{1007}\cdot\frac1{1007}}_{1006\text{ factors}}\;. \end{align*}$$

The $1006$ factors on the left are between $1$ and $2$; the factors on the right are between $1$ and $\frac1{1007}$. Try matching them up.

$\endgroup$
0
13
$\begingroup$

The number you used is still small enough to be calculated directly, so I used Python which have unlimited precision integer arithmetic to get the answer:

>>> math.factorial(2013) < 1007**2013
True

$2013!$ is a 5779-digit number:

2842867247059648714320882908184358975298425936765406743563017882090099387783580447012935263746562335479064550804211732063022834149625421992014144514533688428601587813569194324989561917151782797873121680666949119475158973400795970620477769770891025873157955892369624843826017526081184552011934374105097315782048120736085815132954887354715539226256291405434589203833779899000588701510318939043247864678134992934379533230544528487035914118945693626528290368591437206653279522877509212788210737957582469711071411021659870559714136474522599718501409090834918926679268116898270673098203451361899317085587433326969579362334919786008994344217419373006643085721568389423052059764681667173457445382263982941073416605568659124787280831190799962707336132841922714527968274349029365670003854224300000354656476434833237074182399956043794238102817592695696938568409658563414032484092565521956662668178041307970779320324765661689930554915530050651296122418092217569587585513016160316926502774945085654600201428197370411755207529508851026315971786389387156555114178249936514939656226821498735997768211690336174306416146685126970909294083138552874100725271266747942592189688081230332253100251403373027228801998127490992546175714650004281060557576018602691444874370276588961454729805801934914327058639037910641855479898434777131761105855951851430766729127680477612727441963181686830328681323514755070052559807855504808093205862574423306499683388729703624875824538600644082634581722622520635413894047216544019784438604398781448535720783960899315838792367983940191638537067898701245056584637806237613648468018169610742424883398829055732890553015662215573197318332952206241281889197604097179798088111804842744903817885667786672979352296770176797979680935970290662288862203487507979401519096847866678683866374334376409418963307236435361004707445941188594507325969642135133107415655296396624159611926210964204186787681300922165759386829935051758089290240223443538483111578632645575815706664545129018761043826893436452374686888469782790455363052163042518632450978515011042593378534376399702189202730567458796342736238859771708958480074038980187180566104679718225155832885875853654917359185418511438742450543999277408460122783085081722502691860182351628742942469052052715157975688543334095817706215356800313073446341193079209893599903066070195526563109494839115954474386835501264382220444236657418730177384297639296031881749231727029032121673951831434276019390206305794145748383191826612485618071270887347907256258516351143901013690471344368527519645321897619683156486225698317847429747071787435782505800084184225460708682095870996428539068134492961102165074890654386785683264530894831563132549697850639084675795153902191945156201050737533340297121449992322830373504638815285378819787554773575857714346271171627666997528270237625481717740484365952887157175985255192895785552274978335022571528293668119818363728825071916771945692681017826150901126099177461980958354110093788032189674991888570154690670597564487340888355272446828142492550508568505273063085689193317985522452127020856295149656879145397271909956463955318885551026529470343326333517019087867518976826084475341789777460562332134901190219314055148808405315658894204410944546182332408944358895866945504173885656268982293387670502772134839209278543053623115562418454749334700318355178628414168339732521747171855166109477719366226966982601829031348339568014756885616782225353731679589010642963026728648636517643953417223323299231306423925974998506982248088188586105779494525593610906456801237689150909962837142846451849955648319845974068370644068187479029156569762901273685536943757280003362988100863219269554589016589760560713983742575493275626526617700401513433557529843197510279124020494964257680880911644344603495723958279131978382862453869345658201667502410202572628757335499674300863432592256152060213732587660770868535439645357581075380700393727832817791761732689216175521623731997708698450168187892421709215550480506135272662476910084841930084011031354220700664181552094272535475251690999640528044608914938782665232028970687185403776703990325979508532509493002666906494481541013473948623057439067716354970459715223485500393463339996144504094685302690606100003782316415853025878871684344019606419775272528889669587663352056426642112160119700550423526808274366819908984680988815165676455989729650205942158024441753903462713582925148615281566818726873632617486647784105131818236742851031943060670450995458031472353966387062287071892889526379622030471150370864215268673980706329585427011992451333823961336244992035822313120108408842120520563544476799611543060018205099439432597579853313019154300707372638257691230423084283981806019389567318013796940093147068650783769412807683958066857778735252857988431592811150528499154617178393545996237667501439149410415620227944238095379762968189409689341536890547638203388318768592606767408394815503891306346323652116455703172953351201933588474955527563220129086963377342371823922961841428147215856281545446983868005765000965710748347784855863778139511179159754686588299301850513114088473086011993200873704826365083841064351095378526835498963203426650033008917628965391592199416177660939562162051582018360903009409052540002566924884243359804526539615984308373031809595967024782906756331879790638545240064000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

and $1007^{2013}$ is a 6046-digit number:

1254077062234018664294785651079353188661191253077799305813791179757827463805186107123273469774162053903664126567921214880932033405051028243615555397191501959364260106323003928599321002731683322949401999655210502809391744938419939018062738332716366402862880435215757453526985197860524118819294856127983255449949193650466469255920307637671989347192990896564831802193303662637471689858254881775308294931056314593558865859412277846959220316005981991390982043618484260701527330998191987467670734150735766216923294907326388071204275065828937002604828333415487795152122447781503832845594360026617507351283224921016611198831493030930482195981758131055818183689747995890365665651476279107424815287868636869361109928506681347743777119911720132660544786046218432565571441788621430604080484938296203394568060167964785329734766682282445348709796311930462634881013620799365053586508918742531723995580514506325855051297836741601484053866007270315702659026879500727872982925399920306004878569195371804797878588169806567743471607652184903935654682366878336922402095873725066023455495673971680917796870931989176869557339483808437125303744424285889537229059044642619648346914283225579841167348374992396139883093953597883022026613940909947963260200934055450518189836603255679961651932234043789207830810500983315729153195086873796101945746271571105969760560558474673462457192842307025382204408978139985316942634976642696036239694144802494437380633345270055518155661872599561602782831551015854360376852362198896088054294108745846372323744868111779302301864828787034294538431186740805407729221221092538026610307411284872463533074716183039238718934453105503115709074759891549572607475746124270904154617269282872431064418760657404943480376703772394830193542534923980294703200491989399888455519264140725015754438747808490754728228195350542284145885146267518973437142106052965376474697334769168078268439588720063899784678392463212420153271604344951195777099867103623029181256151565863342264358081103237677899742532254307011324297851932605737227757619582331337362937202532037703048994339486133351010395772589097738332078010937742001223138688103191338342016785546900286887136413546084102031478154802148593745011803049117248676268520024590101720302210022081475333049718624066089674062339696325767097320420574921212807053142397684107734692334589019508892436814513380209413333453786423301951317137931891144843941999224066924978701376539166863878436638601701149605461021309499531787007846991933987071139677327921044398530866847373830423887250132287581263056656330966554043980448894179103876180623542842106741176314281809495369002279509221037486496596955173870525460524772056062504996865599953381096312159510398668632636326635924938223389930395009279514608451353740725644669388264752061527944515458934134755626289255108836185121181184771576773846759018536287713620889223168938672514694830372923580040447527541497662746632526708920356778364570989755375348227324020290841706263402796453293081118866793817143965736955172622174740444427031100329692640572755726817645010476582861227308515667802309657213140529686619834758739065976720196399633029535094253444926481466810780444244506651281597693304907651855435795031368128636595839631205160309268803623825508414597916068816007830441724538944386987289758171996686036713977272268646097771933369950689231167653218368972662225033955287213444724587151129746063815151987603860878929743338699908308213846772881078076016654224992774474893780414856861418455758568555928120853996519570672171135232192319764377771865970942726057599666718258918406651223051636668412913474708138660886580985263085546458982296702137142351206696579031799556344824693240625077672709659998286725205509004830283197656903210582839563024232260326592755819473303383861527676998860545687645063318748530283405739793881025113444235717005666171205502713236894663824491695609417795380474164484646718590655302439605575575371575190405753148769483641795899660373967428060040657788737371116632866491256511158413866009194798597271706177322306869490328551607568903292098316666599023140864621617087929484284044079191805672733060081511348697947253411027124095400487245844730801175257983621024331495321786531616922039162913592768005437036481041275536397624907772994016156302190932986173731124327444304040277818998711083692425664802028566451489131922130636636327563058454100774790799030269611864727408707351741506510886801258224862130027819283629664430853185028196475323927825645459324714912369287899965129702587231534413346068078071518958842837313964017533052262604062216656395585843290878941151226327711912006654248000259908343491817913738717623629395442227942426634340036550828286035706571666464019197391502525331099640527493538152573209417865496959413035205251586141604510088834715910222799628803671089096203917892278218637191531064384904735895114668153361973352671866331933881048725186878743302851254928849660548950182980650988678881513724457558500306380451748079702690841426996917746250140820949864212459490851194295326298407959166994678124062954645120169535398298326186505351074592825566199265656946613452548948534151260010320428615602375922449959528121345645656036240327305610913191542364814975638640957196282843109231098728911165032474497262564587617903567623596507776203179936752166935493243612412572755693801253946291880554162232260976473100856265074690226644201344422886699749786632140170441912870937520769401612321569315634069706252655232184526258820931655837569433016986808676056526441898453784579526465891728693409412342325001443476462133136036423272384616019285378916897482032237882469062690699463170030720690767269771796023506960831459770328555781757419953133476243911399708997411118725821041780892616383234477816941928700326078397932007910398989221754941944886038634892813759031353686327338993821517941892809240416797651348177227471627413774344737866286577428297915594350331614454200789271020195739795319814256528806892687026301887805025454697821864351543821489137188302711156184139986445544510635013358045665197245162781538704101556709236428952277564431765848892987023407

(though I guess this is not really what you're looking for)

$\endgroup$
1
  • 1
    $\begingroup$ Better tag this one intuition. $\endgroup$
    – Alexander Gruber
    Mar 8, 2013 at 21:04
8
$\begingroup$

Let $j \in \{1,2,\dots,2013\}$.

When $j$ is small, $1007$ is much larger in size than $j$. [For e.g. $1007 = 1007 \cdot 1$] So for small $j$, the $j$-th factor in $1007^{2013}$ is much larger in size than the $j$-th factor in $2013!$.

But when $j$ is large, $j$ is not that much larger than $1007$. [For e.g. $2013 < 1007 \cdot 2$] So for large $j$, the $j$-th factor in $2013!$ is not that much larger in size than the $j$-th factor in $1007^{2013}$.

Does this line of reasoning help you find an answer to this question?

[Notice also that $1007$ is the median (midpoint) of $\{1,2,\dots,2013\}$.]

$\endgroup$
3
  • $\begingroup$ I upvoted, but you should change term to factor. $\endgroup$ Mar 8, 2013 at 15:40
  • 1
    $\begingroup$ Also, "median" isn't really the key. If $a_1,\dots,a_{2013}$ is a set of positive numbers with mean $1007$ then it is still true that $a_1\dots a_n \leq 1007^{2013}$. $\endgroup$ Mar 8, 2013 at 15:46
  • $\begingroup$ Thanks Brian & Thomas - have edited my answer accordingly to take in your comments. $\endgroup$
    – Conan Wong
    Mar 9, 2013 at 15:23
3
$\begingroup$

Hint: Use the inequality $k(n-k)\le (n/2)^2$. Then you could prove the more general inequality (without Stirling).

$\endgroup$
3
$\begingroup$

$1007^{2013}=(2013-1006)(2012-1005)(2011-1004).....(1008-1)$

$2013!=(1007+1006).(1007+1005).(1007+1004)....(1007-1006).(1007)$

$(1007^2-1006^2).(1007^2-1005^2).(1007^2-1004^2)...(1007^2-1^2).1007<(1007^2)^{1006} .1007$

$<1007^{2013}$

$\endgroup$
0
2
$\begingroup$

A mere generalization, using Stirling's approximation again:

$$ n! \ \text{vs} \bigg(\frac{n}{2} \bigg)^n\\ \bigg(\frac{n}{e}\bigg)^n \sqrt{2 \pi n} \ \text{vs} \ \bigg(\frac{n}{2} \bigg)^n\\ 2 \pi n \ \text{vs} \bigg(\frac{e}{2} \bigg)^{2n} $$ LHS is $f(n)=2 \pi n=O(n)$, RHS is $g(n)=(\frac{e}{2} )^{2n}=O(a^{2n}), \ a>1$, so $f(n)=o(g(n))$. In fact this holds already for $n=6$.

$\endgroup$
1
  • 1
    $\begingroup$ It's actually $\left(\frac{n+1}2\right)^n$. $\endgroup$ Mar 8, 2013 at 15:53

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.