A probability problem by George G

Probability Level 4

Find the last three digits of the sum ∑ i = 1 1505 ( 3010 − i i ) . \sum_{i=1}^{1505}{3010-i\choose i}.


The answer is 88.

George G by George G , 57, USA

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.

1 solution

Piyushkumar Palan
Dec 29, 2013

I tried with smaller numbers first with hope to get some pattern.

∑ i = 0 1 ( 2 − i i ) = 2 \displaystyle \sum_{i=0}^1 {2-i \choose i} = 2

∑ i = 0 1 ( 3 − i i ) = 3 \displaystyle \sum_{i=0}^1 {3-i \choose i} = 3

∑ i = 0 2 ( 4 − i i ) = 5 \displaystyle \sum_{i=0}^2 {4-i \choose i} = 5

∑ i = 0 2 ( 5 − i i ) = 8 \displaystyle \sum_{i=0}^2 {5-i \choose i} =8

∑ i = 0 3 ( 6 − i i ) = 13 \displaystyle \sum_{i=0}^3 {6-i \choose i} =13

Pleasant shock to get fibonacci numbers as answers. (don't know the proof.)

Above 5 answers being F 3 , F 4 , F 5 , F 6 , F 7 F_{3}, F_{4}, F_{5}, F_{6}, F_{7} respectively.

So predicted ∑ i = 0 1505 ( 3010 − i i ) = F 3011 \displaystyle \sum_{i=0}^{1505} {3010-i \choose i} = F_{3011} ⇒ ∑ i = 1 1505 ( 3010 − i i ) = F 3011 − 1 \Rightarrow \displaystyle \sum_{i=1}^{1505} {3010-i \choose i} = F_{3011}-1

On searching, got F 3011 F_{3011} as

8171462471 9597865751 2856492896 3621698483 7433583353 0189695852 9783427309 5195424751 1135072102 1883373646 5656420211 4139242218 9009640546 5503647355 5062125350 7928250454 2544299881 2118369050 7647932369 4932406212 2053646388 7276755400 3457230882 2593382656 0533673155 6372981610 2926727398 5536440976 8603291121 7780167413 3799363837 4745763941 6046397414 4620863047 6861321736 2578575541 7191868544 0536401777 3929049738 4643721693 4209676460 5686277794 7796739440 5590490481 6667368549 7736402901 8286868401 4600574275 9147927356 8846049097 9781358626 3536257538 6220925688 0158636896 0584209597 6827264761 0222794912 5358763002 6115261547 6524469556 8853790570 6209825207 514702089

So answer: 088 \boxed {088}

5 Helpful 0 Interesting 0 Brilliant 0 Confused

The summation is simply the manipulation of the sums of "shallow" diagonals in Pascal's triangle

The expression is simply F 3011 − 1 F_{3011} - 1 , now we consider finding F 3011 ( m o d 1000 ) F_{3011} \pmod{1000}

By Pisano Period , π ( 8 ) = 12 \pi(8) = 12

F 3011 m o d 8 = F 3011 m o d 12 m o d 8 = F 11 m o d 8 = 89 m o d 8 = 1 F_{3011} \bmod 8 = F_{3011 \bmod 12} \bmod 8 = F_{11} \bmod 8 = 89 \bmod 8 = 1

And (in the same article), For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4. Also, it can be proven that π ( n ) ≤ 6 n \pi (n) \leq 6n , with equality if and only if n = 2 ⋅ 5 k n = 2 \cdot 5^k , for k ≥ 1 k \geq 1

So π ( 250 ) = π ( 2 × 5 3 ) = 6 ⋅ 250 = 1500 \pi(250) = \pi (2 \times 5^3) = 6 \cdot 250 = 1500

⇒ F 3011 m o d 250 = F 3011 m o d 1500 m o d 250 = F 11 m o d 250 = 89 \Rightarrow F_{3011} \bmod {250} = F_{3011 \bmod {1500}} \bmod {250} = F_{11} \bmod {250} = 89

So the possible last three digits of F 3011 F_{3011} are either 89 , 89 + 250 , 89 + 500 , 89 + 750 89, 89+250,89+500,89+750

But because F 3011 ( m o d 8 ) = 1 F_{3011} \pmod{8} = 1 , then F 3011 ≡ 89 ( m o d 1000 ) F_{3011} \equiv 89 \pmod{1000}

Hence, ( F 3011 − 1 ) m o d 1000 = 88 (F_{3011} - 1) \bmod{1000} = \boxed{88}

Pi Han Goh - 7 years, 5 months ago

OK, I guess it can be calculated using programs. See here . But there is mathematics to it.

George G - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...