# Solution 86: Double Factorial and Roots of Unity Filter (Proof)

Embed

- Published on Apr 4, 2019
- We prove the roots of unity filter and apply it to evaluate a fascinating summation.

Congratulations to Gabriel N., Essentials of Math, Peter, fmakofmako, Hiren Bavaskar, Paco Libre, aby p, santosh tripathy, Proof by Meme, and Mushishi2872 for successfully solving this math challenge question! Gabriel N. was the first person to solve the question.

Your support is a heartfelt source of encouragement that propels the channel forward.

Please consider taking a second to subscribe in order to express your valuable support and receive notifications for the latest videos!

Any likes, subscriptions, comments, constructive criticisms, etc., are very much appreciated.

For more Weekly Math Challenges:

usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

KichiheiMonth agoOmg!

-Month agoIt's not everyday you see e raised to a primitive root of unity ;)

Jeffrey Hersh4 months agoThis inspired me to try to find the general solution for any S(a) = Sum[1/(2an)!!, {n,0,Infinity}] where a is a positive integer.

Turns out with some cleaver manipulation of the sum after applying the filter it generalizes to:

S(a) = (1/a) Sum[e^((1/2) cos (k theta)) e^((i/2) sin (k theta)),{k,0,a-1}] = (1/2) Sum[f(k),{k,0,a-1}] (where theta is 2 pi/a)

which simplifies by noticing that f(k) + f(a-k) = 2 e^((1/2) cos(k theta)) * cos[(1/2) sin (k theta)]

thus (after manipulating and shifting the index of the sum)

S(a) = (1/a)(e^1/2) + (2/a) Sum[e^((1/2) cos(m theta)) * cos((1/2) sin(m theta)),{m,1,k}]

where if a is even, k = (a/2), and if a is odd k = (1/2)(a-1)

and theta = 2 pi/a

Plugging in a = 3 (as in the video) we get

S(3) = (1/3)(e^(1/2)) + (2/3) e^(-1/4) cos(sqrt(3)/4)

Hilda Gani4 months ago^{+1}Can you make a video about Roots of Unity filter?

Hiletso Eu5 months agoExcellent video

Sitanshu Chaudhary5 months ago^{+2}Make a only video on roots of unity filter please

Jeff Ahn5 months ago^{+1}Roots of unity filter -- just amazing!

Aaron He5 months ago^{+1}Surprising how a square root ended up inside the cosine function!

Richard Reynolds5 months ago^{+3}An unusual radian angle answer; but if it works, it works.

Hansen Chen5 months ago^{+1}It is not unusual. It is a special case of the discrete Fourier expansion.

steamroller825 months agoBeautiful. Well done sir!

Johannes H5 months ago^{+2}Awesome, but I couldn't gome up with that myself

Davide5 months ago^{+2}Neat

Risu0chan5 months ago^{+15}I love it so much when I learn new techniques. And it comes with a well explained proof

Chan Dan5 months ago^{+8}Can you refer any book where I can find cube root of unity filter. I have never heard of it !

Chan Dan5 months ago@Hansen Chen sorry sir ! I have not taken the linear algebra course.

Hansen Chen5 months ago^{+1}@Chan Dan Do you see that our problem is but the orthonormality between the zero'th basis vector and all the other basis vectors (unit roots) of the discrete Fourier transform?

Hansen Chen5 months ago^{+1}@Chan Dan Just check the Wikipedia page for the discrete Fourier transform, particularly the orthogonality of the basis en.wikipedia.org/wiki/Discrete_Fourier_transform#Orthogonality and the references therein. That is a special case of the expansion of the Dirac or Kronecker delta function as I mentioned before.

Chan Dan5 months ago@Hansen Chen ok ! Can you provide any specifications like author or publisher etc. ? I did not get what fourier analysis to do with cube roots of unity.

Hansen Chen5 months ago^{+1}You can check out discrete or fast Fourier analysis. Any summation expansion of the Dirac delta function is a generalization.