Super Duper Hedral Sum

Probability Level 5

a 1 , n = 1 + 2 + 3 + … + n a 2 , n = a 1 , 1 + a 1 , 2 + a 1 , 3 + … + a 1 , n a 3 , n = a 2 , 1 + a 2 , 2 + a 2 , 3 + … + a 2 , n a 4 , n = a 3 , 1 + a 3 , 2 + a 3 , 3 + … + a 3 , n ⋅ ⋅ ⋅ a 1000 , n = a 999 , 1 + a 999 , 2 + a 999 , 3 + … + a 999 , n \large{\begin{aligned} a_{1,n} &=& 1+2+3+\ldots+n \\ a_{2,n} &=& a_{1,1} + a_{1,2} + a_{1,3} + \ldots + a_{1,n} \\ a_{3,n} &=& a_{2,1} + a_{2,2} + a_{2,3} + \ldots + a_{2,n} \\ a_{4,n} &=& a_{3,1} + a_{3,2} + a_{3,3} + \ldots + a_{3,n} \\ & \cdot & \\ & \cdot & \\ & \cdot & \\ a_{1000,n} &=& a_{999,1} + a_{999,2} + a_{999,3} + \ldots + a_{999,n} \\ \end{aligned}}

If we are given the 1000 equations above, evaluate the expression below.

( 1000 ∏ k = 1 1000 k + 1000 k ) ÷ a 1000 , 1000 \large \left (1000 \prod_{k=1}^{1000} \frac{k+1000}k \right) \div a_{1000,1000}


The answer is 1001.

View wiki
Pi Han Goh by Pi Han Goh , 30, Malaysia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Jason Zou
Aug 5, 2015

We can see that a 1 , n = ( n + 1 2 ) a_{1,n}=\binom{n+1}{2}

Now assume that a k , n = ( k + n k + 1 ) a_{k,n}=\binom{k+n}{k+1}

Then we have a k + 1 , n = ∑ i = 0 n ( k + i k + 1 ) a_{k+1,n}=\sum^n_{i=0} \binom{k+i}{k+1}

Hockey Stick theorem says that ∑ x = 0 m ( y + x y ) = ( y + x + 1 y + 1 ) \sum^m_{x=0} \binom{y+x}{y}=\binom{y+x+1}{y+1}

In our case, we get that a k + 1 , n = ( k + 1 + n k + 1 + 1 ) a_{k+1,n}=\binom{k+1+n}{k+1+1}

So by induction, a k , n = ( k + n k + 1 ) a_{k,n}=\binom{k+n}{k+1} for all k k and n n .

Now in the final expression, we can see that ∏ k = 1 1000 k + 1000 k = ( 2000 1000 ) \prod^{1000}_{k=1} \frac{k+1000}{k}=\binom{2000}{1000}

From that we get that the value is 1000 ∗ ( 2000 1000 ) ( 2000 1001 ) = 1000 ∗ 1 1000 1 1001 = 1001 \frac{1000*\binom{2000}{1000}}{\binom{2000}{1001}}=\frac{1000*\frac{1}{1000}}{\frac{1}{1001}}=\boxed{1001}

3 Helpful 0 Interesting 0 Brilliant 0 Confused

YAY! CORRECT! I was thinking of Catalan Number for the final step though

Pi Han Goh - 5 years, 10 months ago
Terry Smith
Dec 5, 2015

Hmm - just glancing at the problem I can see the denominator is 2046105521468021692642519982997827217179245642339057975844538099572176010191891863964968026156453752449015750569428595097318163634370154637380666882886375203359653243390929717431080443509007504772912973142253209352126946839844796747697638537600100637918819326569730982083021538057087711176285777909275869648636874856805956580057673173655666887003493944650164153396910927037406301799052584663611016897272893305532116292143271037140718751625839812072682464343153792956281748582435751481498598087586998603921577523657477775758899987954012641033870640665444651660246024318184109046864244732001962029120000 and the numerator is 2048151626989489714335162502980825044396424887981397033820382637671748186202083755828932994182610206201464766319998023692415481798004524792018047549769261578563012896634320647148511523952516512277685886115395462561479073786684641544445336176137700738556738145896300713065104559595144798887462063687185145518285511731662762536637730846829322553890497438594814317550307837964443708100851637248274627914170166198837648408435414308177859470377465651884755146807496946749238030331018187232980096685674585602525499101181135253534658887941966653674904511306110096311906270342502293155911108976733963991149120000 and that times 1000 and divided by the denominator is 1001.

Just kidding - I computed it in Ruby using recursive functions and it took a while too. Thanks!

1 Helpful 0 Interesting 0 Brilliant 0 Confused

HAHAHAH! Upvoted!

Pi Han Goh - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...