Sum it

Algebra Level 4

If k = 0 99 ( 99 k ) \large\displaystyle \sum^{99}_{k=0}\dbinom{99}{k} is divided by k = 0 33 ( 99 3 k ) , \large\displaystyle\sum^{33}_{k=0}\dbinom{99}{3k},
the resulting number is of the form \large{\dfrac{a}{b}} \dot \large {\dfrac{c^d}{(e^f-1)}}, where a , b , c , e \large{a, b, c, e} are prime numbers. Evaluate a + b + c + d + e + f 1 \large{a+b+c+d+e+f-1} .


The answer is 205.

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

Kushal Bose
Dec 26, 2016

We know ( 1 + x ) 99 = ( 99 0 ) + ( 99 1 ) x + ( 99 2 ) x 2 + ( 99 3 ) x 3 + . . . . . . . + ( 99 99 ) x 99 (1+x)^{99}={99 \choose 0}+{99 \choose 1}x+{99 \choose 2}x^2+{99 \choose 3}x^3+.......+{99 \choose 99}x^{99}

Put x = 1 x=1 we get k = 0 99 ( 99 k ) = ( 1 + 1 ) 99 = 2 99 = ( 99 0 ) + ( 99 1 ) + ( 99 2 ) + ( 99 3 ) + . . . . . . . + ( 99 99 ) \displaystyle \sum^{99}_{k=0}\dbinom{99}{k}=(1+1)^{99}=2^{99}={99 \choose 0}+{99 \choose 1}+{99 \choose 2}+{99 \choose 3}+.......+{99 \choose 99}

Put x = ω x=\omega then ( 1 + ω ) 99 = ( 99 0 ) + ( 99 1 ) ω + ( 99 2 ) ω 2 + ( 99 3 ) . 1 + . . . . . . . + ( 99 99 ) . 1 (1+\omega)^{99}={99 \choose 0}+{99 \choose 1}\omega+{99 \choose 2}\omega^2+{99 \choose 3}.1+.......+{99 \choose 99}.1

Now put x = ω 2 x=\omega^2 then ( 1 + ω 2 ) 99 = ( 99 0 ) + ( 99 1 ) ω 2 + ( 99 2 ) ω + ( 99 3 ) . 1 + . . . . . . . + ( 99 99 ) . 1 (1+\omega^2)^{99}={99 \choose 0}+{99 \choose 1}\omega^2+{99 \choose 2}\omega+{99 \choose 3}.1+.......+{99 \choose 99}.1

Adding these three equations we get:

3 k = 0 33 ( 99 3 k ) = 2 99 + ( 1 + ω ) 99 + ( 1 + ω 2 ) 99 = 2 99 + ( ω 2 ) 99 + ( ω ) 99 = 2 99 1 1 = 2 99 2 k = 0 33 ( 99 3 k ) = 2 99 2 3 \displaystyle 3 \sum_{k=0}^{33} {99 \choose 3k}=2^{99} +(1+\omega)^{99} + (1+ \omega^2)^{99} \\ =2^{99} +(-\omega^2)^{99} +(-\omega)^{99} \\ =2^{99} -1-1=2^{99}-2 \\ \implies \displaystyle \sum_{k=0}^{33} {99 \choose 3k}=\dfrac{2^{99}-2}{3}

After dividing 3. 2 99 2 99 2 = 3 2 2 99 2 98 1 \dfrac{3.2^{99}}{2^{99}-2}=\dfrac{3}{2} \dfrac{2^{99}}{2^{98}-1}

Note ω \omega is the cube roots of unity and 1 + ω + ω 2 = 0 1+\omega + \omega^2=0

A nice solution... +1 .

Sabhrant Sachan - 4 years, 5 months ago

@Akeel Howell Note that your final form is not unique, since we could have multiple versions for e f + g e^f + g , like e = 2 , f = 97 , g = e 97 1 e = 2, f = 97, g = e^{97} - 1 .

Can you figure out how to make it unique? I think the simplest way is to give the value of g = 1 g = -1 .

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

Thanks for mentioning that. I added the parameter that g g must be < 0 <0 .

Akeel Howell - 4 years, 5 months ago

Log in to reply

Just having g < 0 g < 0 is not sufficient either. For example, we could have e = 2 , f = 98 , g = 2 97 + 1 e = 2, f = 98, g = 2^{97} + 1 (excuse any calculation errors).

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

@Calvin Lin I'm failing to see how setting e = 2 , f = 98 , g = 2 97 + 1 e=2, f=98, g=2^{97}+1 fixes it. This changes the value of the expression and makes g g a positive integer.

Akeel Howell - 4 years, 5 months ago

Log in to reply

@Akeel Howell Oh sorry, I meant to say e = 2 , f = 99 , g = ( 2 98 + 1 ) e = 2, f = 99, g = - (2^{98} + 1 ) is also a possibility. Was looking at the wrong indices.

Other possibilities include e = p , f = N > 98 log p 2 , g = ( e f 2 98 + 1 ) e = p, f = N > 98 \log_p 2, g = - ( e^f - 2^{98} + 1 ) for any prime number p p and integer N N .

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

@Calvin Lin I see. I will set g = 1. g=-1.

Akeel Howell - 4 years, 5 months ago
Akeel Howell
Mar 5, 2017

\\ \large\displaystyle \sum^{99}_{k=0}\dbinom{99}{k} = (1+1)^{99} = (2)^{99} \\ \large\displaystyle\sum^{33}_{k=0}\dbinom{99}{3k} = \dfrac{(1+1)^{99}+(1+\omega)^{99}+(1+\omega^2)^{99}}{3}, \text{ where } \omega \text{ is a third root of unity } \\ = \dfrac{2^{99}+(-\omega^2)^{99}+(-\omega)^{99}}{3} = \dfrac{(2^{99}-1-1)}{3} = \dfrac{(2^{99}-2)}{3} = \dfrac{2(2^{98}-1)}{3} \\ \therefore \large\displaystyle \sum^{99}_{k=0}\dbinom{99}{k} \text{divided by } \large\displaystyle\sum^{33}_{k=0}\dbinom{99}{3k} = \dfrac{3\times 2^{99}}{2\times (2^{98}-1)} = \large{\dfrac{3}{2}} \dot \large {\dfrac{2^{99}}{(2^{98}-1)}}. \\ \text{So } a = 3, b = 2, c = 2, d = 99, e = 2, f = 98 \implies 3+2+2+99+2+98-1 = \boxed{205}


Note: We do not simplify the final term any further to preserve the form of the solution in the problem. 1 1 is not a prime number.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...