A Nice Problem!

Algebra Level 2

n = 0 7 ( 30 4 n ) \large \sum_{n=0}^{7}\dbinom{30}{4n}

If the value of the summation above can be expressed as 2 a 2^a , find the value of a a .


Hint: Complex numbers


The answer is 28.

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.

3 solutions

Pi Han Goh
Aug 14, 2015

Let I I denote the summation. Apply the property of binomial coefficient: ( n a ) = ( n n a ) \dbinom{n}{a} = \dbinom{n}{n-a} .

I + I = n = 0 7 ( ( 30 4 n ) + ( 30 30 4 n ) ) 2 I = n even ( 30 n ) 2 I = k ( 29 k ) since ( 30 n ) = ( 29 n 1 ) + ( 29 n ) 2 I = 2 29 I = 2 28 \begin{aligned} \displaystyle I + I &=& \sum_{n=0}^7 \left(\dbinom{30}{4n} + \dbinom{30}{30-4n}\right) \\ \displaystyle 2I &=& \sum_{n \text{ even}} \dbinom{30}{n} \\ 2I & = & \sum_k { 29 \choose k } & \text{ since } { 30 \choose n} = {29 \choose n-1} + { 29 \choose n } \\ \displaystyle 2I &=& \cdot 2^{29} \\ I &=& 2^{28} \\ \end{aligned}

That is probably the most elegant method to solve this problem!Lovely!+1

Adarsh Kumar - 5 years, 10 months ago

As simple as that. Did it mentally. yay !

Keshav Tiwari - 5 years, 10 months ago

2^30/2=2^28?

Aditya Agarwal - 5 years, 10 months ago

Log in to reply

No , you missed the two on the left.

Keshav Tiwari - 5 years, 10 months ago

Where does the formula come from? ;_;

Lucyana Can D Vith - 5 years, 9 months ago

Can you explain your second and third step

Puneet Pinku - 5 years ago

Log in to reply

Second step = Write out all 8 terms for this summation.

Third step: Apply pascal's rule, see the line: "since ...."

Pi Han Goh - 5 years ago

Log in to reply

I don't know pascals rule but I see that your since statement is true. But from that how did you come to 4 and 5 statement. I am not able to figure out. Please elaborate.

Puneet Pinku - 5 years ago

Log in to reply

@Puneet Pinku Sum of all the entries in the n th n^\text{th} row of a Pascal's triangle is equal to 2 n 2^n . In this case,

( 29 0 ) + ( 29 1 ) + ( 29 2 ) + ( 29 3 ) + + ( 29 29 ) = 2 29 . \dbinom{29}0 + \dbinom{29}1 + \dbinom{29}2 + \dbinom{29}3 + \cdots+ \dbinom{29}{29} = 2^{29}.

Pi Han Goh - 5 years ago

Sorry, I don't understand the second step...

Saurabh Chaturvedi - 5 years ago

Log in to reply

Write out all the terms in the summation in my first step. Show that it is equal to the second step.

Pi Han Goh - 5 years ago

Could you also provide a solutions to this problem Disturbing coefficients

Puneet Pinku - 5 years ago
Chew-Seong Cheong
Aug 13, 2015

( 1 + i ) 30 = n = 0 30 ( 30 n ) i n ( 2 e π 4 i ) 30 = 1 + 30 i 435 4060 i + . . . 4060 i + 435 + 30 i 1 2 15 e 15 π 2 i = n = 0 7 ( 30 4 n ) + i n = 0 7 ( 30 4 n + 1 ) n = 0 7 ( 30 4 n + 2 ) i n = 0 6 ( 30 4 n + 3 ) 0 2 15 i = S 0 + S 1 i S 2 S 3 i S 0 = S 2 \begin{aligned} (1+i)^{30} & = \small \sum_{n=0}^{30} \begin{pmatrix} 30 \\ n \end{pmatrix} i^n \\ \left(\sqrt{2}e^{\frac{\pi}{4}i}\right)^{30} & = 1 + 30i - 435 - 4060i +...-4060i+435+30i-1 \\ 2^{15} e^{\frac{15\pi}{2}i} & = \small \sum_{n=0}^7 \begin{pmatrix} 30 \\ 4n \end{pmatrix} + i \sum_{n=0}^7 \begin{pmatrix} 30 \\ 4n+1 \end{pmatrix} - \sum_{n=0}^7 \begin{pmatrix} 30 \\ 4n+2 \end{pmatrix} - i \sum_{n=0}^6 \begin{pmatrix} 30 \\ 4n+3 \end{pmatrix} \\ 0 - 2^{15} i & = S_0 + S_1i - S_2 - S_3i \\ \color{#3D99F6}{\Rightarrow S_0} & = \color{#3D99F6}{S_2} \end{aligned}

Now, we have:

{ ( 1 + 1 ) 30 = S 0 + S 1 + S 2 + S 3 = 2 30 . . . ( 1 ) ( 1 1 ) 30 = S 0 S 1 + S 2 S 3 = 0 . . . ( 2 ) \begin{cases} (1+1)^{30} = S_0 + S_1 + S_2 + S_3 = 2^{30} &...(1) \\ (1-1)^{30} = S_0 - S_1 + S_2 - S_3 = 0 &...(2) \end{cases}

( 1 ) + ( 2 ) : 2 S 0 + 2 S 2 = 2 30 4 S 0 = 2 30 S 0 = n = 0 7 ( 30 4 n ) = 2 28 \begin{aligned} (1)+(2): \quad 2S_0 + 2S_2 & = 2^{30} \\ 4S_0 & = 2^{30} \\ \Rightarrow S_0 & = \color{#3D99F6} {\sum_{n=0}^7 \begin{pmatrix} 30 \\ 4n \end{pmatrix} = \boxed{2^{28}}} \end{aligned}

Moderator note:

Standard approach using the roots of unity to sum up such periodic terms with the proper generating functions.

Excellent solution. However in line 4, 0 2 14 i \ 0-2^{14} i should be 0 2 15 i \ 0-2^{\boxed{15}} i . Please fix so that people do not get confused.

Isay Katsman - 5 years, 10 months ago
Curtis Clement
Aug 12, 2015

The sum was relatively small so I was able to use a calculator to obtain a = 28. However, when I tried the complex approach all I got was ( 1 + i ) 30 = i ( [ ( 30 1 ) + ( 30 5 ) + . . . + ( 30 29 ) ] [ ( 30 3 ) + ( 30 7 ) + . . . + ( 30 27 ) ] ) \ (1+i)^{30} = i ( [ {30 \choose 1 } +{30 \choose 5 } +...+ {30 \choose 29 } ] - [{30 \choose 3 } +{30 \choose 7 }+...+{30 \choose 27 } ]) = 2 15 i \ = 2^{15} i I also tried the same for (1-i) but ended up with the same result. What am I missing?

To understand the hint, evaluate

1 n + i n + ( 1 ) n + ( i ) n . 1^n + i^n + (-1)^n + (-i)^n.

Hence, the answer is ( 1 + 1 ) 30 + ( 1 + i ) 30 + ( 1 1 ) 30 + ( 1 i ) 30 4 \frac{ ( 1 + 1) ^ {30} + ( 1 + i ) ^ {30} + (1-1)^{30} + (1 - i ) ^ {30} } { 4} .

Calvin Lin Staff - 5 years, 10 months ago

I have never seen any problem in brilliant which provided hints :/

Satyajit Mohanty - 5 years, 10 months ago

Log in to reply

See this I guess if hint was not given , very very less people would have been able to solve it.

Nihar Mahajan - 5 years, 10 months ago

@Curtis Clement first put x=i then x=-i and then x=1 in (1+x)^30 and then add,that is the way to do it.

Adarsh Kumar - 5 years, 10 months ago

Log in to reply

No, it doesn't work. ( 1 + i ) 30 = 0 32768 i (1+i)^{30} = 0 - 32768i and ( 1 i ) 30 = 0 + 32768 i (1-i)^{30} = 0 + 32768i ( 1 + i ) 30 + ( 1 i ) 30 + ( 1 + 1 ) 30 = 2 30 \Rightarrow (1+i)^{30} + (1-i)^{30} + (1+1)^{30} = 2^{30}

( 1 + i ) 30 = ( 2 e π 4 i ) 30 = 2 15 e 15 π 2 i = 2 15 e π 2 i = 2 15 ( cos π 2 sin π 2 i ) = 0 2 14 i (1+i)^{30} = \left( \sqrt{2} e^{\frac{\pi}{4}i}\right)^{30} = 2^{15} e^{\frac{ 15\pi}{2}i} = 2^{15} e^{-\frac{\pi}{2}i} = 2^{15} (\cos{\frac{\pi}{2}} - \sin{\frac{\pi}{2}}i) \\ = 0 - 2^{14}i

Chew-Seong Cheong - 5 years, 10 months ago

Log in to reply

Why is it

2 15 ( cos π 2 sin π 2 i ) = 0 2 14 i 2^{15}(\cos\frac \pi2-\sin\frac \pi2i)=0-2^{14}i

And not

2 15 ( cos π 2 sin π 2 i ) = 0 2 15 i 2^{15}(\cos\frac \pi2-\sin\frac \pi2i)=0-2^{\boxed{\boxed{15}}}i

?????

Cleres Cupertino - 5 years, 10 months ago

Log in to reply

@Cleres Cupertino I believe this is a slight typographical error. I will make a brief post asking for a correction.

Isay Katsman - 5 years, 10 months ago

Log in to reply

@Isay Katsman Yeah! I also believe in this!

Cleres Cupertino - 5 years, 10 months ago

Yea I found that the identities don't lead to any solution.

Curtis Clement - 5 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...