Olympiad level counting (Generating functions) 

"There's life before you understand generating functions, and then there's life after you understand generating functions." Having taken those courses, I can 100% agree.

"The shortest path between two truths in the real domain passes through the complex plane" - Jacques Hadamard. Excellent video!

3:54 "To be clear, this lesson is definitely much more about the journey than the destination". This is the biggest difference between this channel and other channels that show math problems: it doesn't just show you one correct solution to a specific problem, but it teaches you how to think about a new problem. And that is no small feat. Thank you, Grant.

As a freshman, I understand only a quarter of the things this man says, but somehow, I still find myself learning. This is mystifying to me.

There's teaching math, and then there's this channel. This isn't just math education, its a window into the sublime

At exactly 14:31 I realized where you were going. I just love this feeling when it "clicks" and your videos never fail to deliver on that, thank you for this great content!

For me, this is one of the most challenging 3B1B videos to wrap my mind around.

Every time I watch this guys videos I am blown away by how intelligent people can be, how I would never be able to arrive at any of these ideas, and above all the quality of this guy's videos. The production value is through the roof.

Fun fact : Titu Andreescu (the author of the book ) was the coach behind the only perfect win of USA in IMO ( all 6 students got perfect scores )

This channel does not simply teach math, it shows math in all of it’s beauty. I would’ve never knew that I like math so much if not for these videos

Grant, I'm sure you've heard this before, but I want to express how much I appreciate the extra special care you take that even a person with zero mathematical training like myself could follow along a complicated exposition like this. It's invaluable to me (and countless others). I humbly thank you. Also, lovely illustrations! Add the rhetorical style, and it all comes together in a most gratifying, soulful, and rich experience. Somebody in the comments used the word 'sublime', and that's accurate.

@34:11 :: The answer to prob 2 is 3^n . This can be easily done by expanding Σ into 2⁰(nC0)+2¹(nC1)+2²(nC2)+.....+2^n(nCn). If you know binomial theorem ,then you may see that it's in the form of (1+x)^n ,where x=2. Hence,the required answer is 3^n.

I'm an Applied Maths major and sometimes is hard to see why I'm learning about complex numbers, analytic geometry and other things and it's harder to see how they are connected. It's truly beautiful to see how it all comes together, thanks.

I love how this channel embraces the math and ACTUALLY TEACHES. So many channels want to make math/physics fun and approachable but end up sacrificing substantiative content to do so. This channel doesn't compromise and I love it. Keep it coming!!

I'm not the kind of viewer that pauses and try to solve the problems by myself because I know I'm getting nowhere, but I watch all your videos and come back to watch them again after a while and it's surprising that, even if don't remember the steps to the solution, it gets less magical and starts to sound more like something that I would have come up by myself. Thanks!

This channel doesn’t make bad videos. The quality is there in every video. You can tell they are not throwing up videos just to put up content. There’s real effort and thought involved in each video.

People with an electrical engineering background might see the roots of unity just like filtering a discrete-time signal in the z-domain. Super cool to see the parallels with the same math used for something seemingly completely different and explained so well!

every time grant mimics a student like "why do complex numbers show up in a counting problem?" I remember that I spend more time with group theory than many target viewers, because my immediate thought is "well the roots of unity are a really natural analog for modular arithmetic"

Having just finished studying some undergraduate level abstract algebra, this video gave me a greater understanding roots of unity and their applications. Your work never fails to both stimulate the creative mathematician in each of us as well as supplement our previous education with new insight. What a gift this channel is, I cannot wait to see what it continues to give in the future. Thank you, Grant, for everything you do.

I watched this about a year ago and remember having no understanding of anything beyond the generating functions. I watched your lockdown math lectures on complex number fundamentals and have a perfect understanding of the video now. Its a beautiful solution I think it's one of your best yet. Thank you

Once again, 3b1b making math look absolutely beautiful. Viewers should feel lucky at what they're seeing ❤️

I remember a time in math class doing series where I wanted to "filter" only odd numbers for some simple sine series, and ended up using a trick with powers of negative one. It's awesome to learn that not only is that technique actually used in practice, but there's a much cooler version out there as well (and yet another use for Very Cool complex numbers :) )

When I was doing my undergraduate course in physics, I fell In love with complex analysis. A way to re-think older problems (infinite trig integrals etc.) with seemingly disconnected injections of complex numbers. But the fact that they *arent* at all disconnected is the beauty in it. Its not 'imaginary' but a very real expression of the root of mathematics (ergo, logic). Probably one of the hardest courses I took. And absolutely my favourite. I wish I had more opportunity in my professional life to get back into complex analysis. For now I think I'm going to just dig up my old notebooks.

This channel is a true treasure. Thank you so, so much for sharing, educating, and engendering a sense of wonder and discovery in us all. 🌱

this is one of many, many reasons why getting exposed to math competitions at a young age is both really useful and entertaining. Too bad, most secondary school teachers are not educated nor paid enough to perform at this level.

It feels almost impossibly beautiful that everything seems to just work out this way, especially with how cleanly complex numbers work in both the factored version and the expanded version. Math really is crazy.

Man, that was a wild solution! Congrats for the presentention, it was astonishing! Thanks for the video!

I want to thank you for this channel. A video a saw here last year was the spark that was missing to ignite strongly enough my desire to pursue a master degree and, despite all the fears and challenges I knew I'd have to overcome by going through with this, finally apply. And now that I'm here trying to conciliate work with the academic life - and also with having a life -, this is, again, the kind of content that reminds me of the passion I feel for the field and that can feel distant when we're struggling in the routine.

Your videos are like a well narrated detective story where a seemingly difficult problem slowly reveals its solution. It's just mesmerizing.

This might be one of the greatest 3b1b videos of all time. The combination of problem solving and visual beauty is breathtaking.

With some friends we mapped this problem to a constrained spin model and the results gives exactly back the polynomial you were talking about.

When I first encountered this problem (it was in fact the number of subsets of {1 .. 300} whose sum was divisible by 3), I came up with the following solution: Generalized question: How many subsets of {0 .. 3n-1} are divisible by 3? I will call this number a(n). I will call b(n) the number of subsets of {0 .. 3n-1} whose sum has rest 1 modulo 3. For symmetry reasons this is exactly half of all subsets which have a sum not divisible by 3. It follows that a(n)+2*b(n)=2^3n We now look at a(n)-b(n): Simple case: n=1. We consider subsets of U={0..2} Let f(x):=(x+1) mod 3. Then for each subset s let f(s)={f(x)|x€s}. It's easy to see that f³(s)=s for each subset s of U and that exactly one of s, f(s) and f²(s) has a sum divisible by 3 for any s - except s=U and s={}. So of the 8 subsets of U, four subsets have a sum divisible by 3, two have a sum =1 mod 3 and two have a sum =2 mod 3. We see that a(1)=4 and b(1)=2, so a(1)-b(1)=2. We now assume that we know a(n) und b(n) for a specific n. Let s be a subset of {0 .. 3n-1} and s0 be a subset of {0..2}. Let g(s,s0)=s U {3n+x|x€s0}. The sum of g(s,s0) equals the sum of the sums of s and s0 mod 3. It's also easy to see that for every subset t of U={0 .. 3n+2} there is exactly one subset s of {0 .. 3n-1} and one subset s0 of {0..2} with t=g(s,s0). A subset g(s,s0) of U has sum divisible by 3 iff either both sums are divisible by 3 or both sums are not divisible by 3 and have different rests mod 3. This leads to a(n+1)=a(1)*a(n)+2*b(1)*b(n) and b(n+1)=a(1)*b(n)+b(1)*a(n)+b(1)*b(n). From this follows that a(n)-b(n)=2^n for every n. Conclusion: b(n)=(2^(3n)-2^n)/3 and a(n)=(2^(3n)-2^n)/3+2^n It's obviously irrelevant whether we look at the subsets of {0 .. 3n-1} or of {1 .. 3n} The same reasoning also works for primes other than 3 and leads to Let a(k,n) be the number of subsets of {1 .. k*n} whose sum is divisible by k. Let b(k,n) be the number of subsets of {1 .. k*n} whose sum has rest 1 mod k. Then a(k,n) + (k-1)*b(k,n) = 2^(kn) and a(k,n) - b(k,n) = 2n, so a(k,n) = (2^(kn)-2n)/k + 2n which in this case means there are (2^2000-2^400)/5 + 2^400 subsets of {1 .. 2000} whose sum is divisible by 5. Seems I am more Bob than Alice.

This feels very much like my real analysis class: I can see what you're doing and how you got there, and it's very impressive, but there's no way I could do it myself.

26:30 His breath of relief when it all comes together

This is actually insane! When I first watched this video, I was so captivated by generating series and I looked for them in the descriptions of all the math classes at my uni. I found out a class that I was going to take in the Fall introduced them. It ended up being my favourite class so far and we also covered finding the closed form expression for recurrence relations like Fibonacci. I actually love this channel so much

I am really filled with lots of gratitude for you, Grant. This channel is really a boon. You tell us how to see it differently.

Incredible video - I remember the Fourier transform video about "wrapping" functions around the unit circle (in the complex plane) and the complex part of this video was extremely reminiscent of that. So much so that I was able to follow along exactly where it was heading. That's when I realized that your videos have fundamentally allowed me to learn math and truly enjoy it. You are my favorite YT channel by far. THANK YOU!

What I really like about this is that literally anyone who understands the problem can come up with a pretty accurate guess. The error would only be 1/2^1598 of the real answer!

Quick note on the side, this puzzle is also an interesting way to practice dynamic programming, a very important technique in the design and analysis of algorithms. The approach shown in the video is certainly more profound and beautiful.

This channel is so underrated. The way you make something like this so interesting and so fun and easy to watch is so fascinating. Never thought I'd watch 32 minutes of complex math, understand it, and feel entertained while doing so. Thank you sir.

This makes me nostalgic. Remembering my high school days in the IMO training camp, solving these problems. Didn't make it to the team by a few marks, but enjoyed the experience a lot. Those were the days.....

Here's another way to solve this problem, which also gives us the number of subsets whose sum is 1,2,3,4 mod 5 respectively too. The idea is taken from the book titled 'Problems From The Book', co-authored by Titu Andreescu as well: Denote c₀, c₁, c₂, c₃, c₄ as the number of subsets whose sum is 0,1,2,3,4 mod 5 respectively, then taking f(x) = (1+x)(1+x²)...(1+x²⁰⁰⁰) evaluated at ζ, we have, by compiling coefficients congruent mod 5, f(ζ) = c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴. But we know f(ζ)=2⁴⁰⁰ (The video has covered this). Therefore c₀ + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 2⁴⁰⁰, or equivalently (c₀-2⁴⁰⁰) + c₁ ζ + c₂ ζ² + c₃ ζ³ + c₄ ζ⁴ = 0. In the field of rational numbers, the polynomial 1+x+x²+x³+x⁴ is the minimal polynomial of ζ, so whenever ζ is a root of some a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ =0 where aᵢ are rational, then 1 + x + x² + x³ + x⁴ divides a₀ + a₁ x + a₂ x² + a₃ x³ + a₄ x⁴, or simply a₀=a₁=a₂=a₃=a₄. Therefore c₀-2⁴⁰⁰=c₁=c₂=c₃=c₄. Since c₀+c₁+c₂+c₃+c₄=2²⁰⁰⁰, we get that c₀=(2²⁰⁰⁰+4×2⁴⁰⁰)/5 c₁=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₂=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₃=(2²⁰⁰⁰-2⁴⁰⁰)/5 c₄=(2²⁰⁰⁰-2⁴⁰⁰)/5 So, not only have we found the number of subsets that have sum divisible by 5, we also found the number of subsets that sum up to other remainders modulo 5 too, and they are surprisingly evenly distributed! (However, take note that this method only works because 5 is prime, whereby we've used the fact that 1+x+x²+x³+x⁴ is irreducible in Q.)

I might have stumbled upon generating functions, when I attempted to generalise some board game dice probabilities, but I was left at a standstill not knowing where to go... This has given me some Ideas for possibly solving a month long nightmare I had stuck in my head! thank you so much!

I'm a math student and teacher (10-14y/o students). This was one amazing presentation of a "simple" question and a solution I could follow seamlessly even though I'm not a genius nor a professional mathematician. Love the simplicity in the design choices and the passion that was put into this! Always a blast listening to your work!! Love from Austria ;)

I'm so excited for that Riemann zeta function video - the old one on analytic continuation is one of my all time favourites on this channel, I watched it just after learning what complex numbers even are. And now look how far we've come... I've even come to actually _like_ complex numbers in the mean time...

As always, really loved it ! The quality just keeps improving beyond what I would've expected. One of my teachers recently had show me the complex roots of z^n=1 and their circular representation, didn't expect to see that in use so quickly. Thanks for the great contents you're making !

I got convinced to watch this video because of your tiktok. At 1am. This video was great and really clear. Going to sleep now.

Yeah! New 3blue1brown video= 5 hours of enjoyment and math pondering

I literally cried seeing the solution finally works out. It is so satisfying. Math will never die. Thank you for making this video, for preserving knowledge and stimulating curiosity.

Every new video this man releases is an absolute treat! Thank you 3b1b for bringing such amazing content to the public.

I've been watching this channel since i was in my second last year of highschool, I'm now in my third year of my bachelor's in pure math and this channel still amazes me every time, the videos are accessible even to people with hither to no background in mathematics and yet are full of insights that even three years after embarking on a formal education journey in pure maths, the quality and entertainment value of the videos on this channel never ceases to amaze me

Watching this while taking a course on groups, rings and fields ended up surprising me in the similarities between this and the Galois groups of field extensions. I think a video on abstract algebra could end up very interesting

There’s another nice way of solving this problem in log(n), where n is the size of the set (in this case, 2000) by exponentiating a 5x5 matrix! Generating functions are fun as well :)

The complex number method is so brilliant, I don't find words to express how beautiful I find it, thank you for sharing all this with us

Another fun way to get g(x)=2 would be to return to the simplified problem about {1,2,3,4,5} [where g(x)=(1+x)(1+x^2)...(1+x^5)]. We know the answer in this smaller case is 8. Therefore, (g(ζ)+g(ζ^2)+...+g(ζ^5))/5=8. From here we get g(ζ)=(40-2^5)/4=2. Thanks for your stunning show, and a special thanks for the puzzles at the end!

Fantastic explanation. You took me from "I have no idea" to "oooooohhhh I could have come up with that" in 20 minutes!

16:19 - The reasoning of this “trick” is just perfect. This makes this whole process much more intuitive.

Loved this - I began to get a Fourier-related hunch as soon as I saw frequency on a circle. This video made the "e-to-the-2-i-pi" stuff really pop into view properly for me - revealing more about circle equations, and the relationship between trig functions and exponents - an area I've been interested in understanding for a while.

This has to be among the highest forms of education ever made, amazing content as always dude

Beautiful video. The answer is striking and as another poster mentioned, it is reminiscent of Burnside's theorem. I'll outline a solution below. Imagine 400 "concentric" pentagons. Label the vertices of the innermost pentagon 1-5, with 1 at the top, proceeding clockwise. On the next largest pentagon, label the vertices 6-10, 6 at the top, proceeding clockwise again. Now, color the vertices with one of 2 colors, say red or green. If the pentagon is fixed, there are 2^2000 ways to do this. When vertex is green, include it in the subset, exclude if it's red. Consider two colorings equivalent if one can be obtained from the other by a rotation of 0, 72, 144, 216, or 288 degrees. By Polya's enumeration/Burnside, there are (1/5)*(2^2000 + 4*2^400) ways to color the vertices. The catch is that in each group of equivalent colorings, one and only one set of green-colored vertices will be a multiple of 5. Thus, the number of colorings is equal to the number of subsets whose sum is a multiple of 5. To see this a bit better, for the simpler {1,2,3,4,5} case, consider just one pentagon and suppose three consecutive vertices are colored green, the other two red. This corresponds to the five 3-element subsets {1,2,3}, {2,3,4}, {3,4,5}, {4,5,1}, and {5,1,2}. Only one of these, {4,5,1}, has a sum that is a multiple of 5. Edit: Spelling

Thank you so much for coming to Tufts! It was so great seeing your work and meeting you! I also love how you’re incorporate the “live” elements where you can see the use of a cursor like in a more traditional lecture to expand and clarify elements. Such a great style!

This was one of the tougher videos for me to get through. It took a few attempts, however, my final watch through I feel like I unlocked a bit of knowledge for myself. Thanks. :)

Hugely appreciate the retrospective of what is implied and learned from solving this puzzle! It's one thing to solve it, but it's another to take away learnings from the solution :)

This reminds me a lot of Burnside's theorem, without having to go through understanding groups, orbits, or stabilizers. Amazing video!

The problem was hard enough. Explaining it in such a thorough yet engaging way is even harder. Hats off to 3Blue1Brown for this one.

greatly appreciate the art, the cool pointer, the recaps, and all

In my set of discrete math courses in college, I was fortunate enough to learn about generating functions, and had the wonderful opportunity to explore them more in my senior thesis. My favorite generating functions are the rook polynomials! When you introduced the problem, I was immediately thinking “Hm, how would I make a generating function for that?” Awesome video as always!

"Root of unity filter" is the technique which was used

Absolutely astonished by the visual style of this video and how it differs from others in the channel, it embodies a form of storytelling and the math parts are presented much more like a DIY thing than a "let the screen do the math" which was absolutely perfect for this kind of problem-solving video, looking forward to other beautiful ways you can present math but also more of this kind of style. These type of videos are what embodies my love for math and education and I'm completely thrilled for what other ways of story telling and teaching math you can scheme. Thanks as always Grant, this was amazing.

Just to clarify something: at 28:35, you say that the value of that polynomial is precisely two. When looking at the two equations that you are saying are equal, it appears that they wouldn't be, due to their differing exponents. The key is to remember that the (1+z^0) term on the bottom is the same as (1+z^5) term above.

Just taught generating functions to a student the other day! Prior to watching this video, my favorite example of a generating function approach providing extra value in counting problems was in the study of the integer partitions (because the associated generating function can be simplified like a geometric series), but this complex numbers idea might be just as awesome!

Your ability to explain math in such a visual way is unparalleled. Even if I don't understand the explicit math behind the solution, the visuals help me intuit how the numbers and whatnot play together to create the solution we want. Beautiful job!

The production quality of your videos is so good... I feel so privileged to be able to watch this for free! The quick Python animations, the cutesy drawn animations, the beautiful music, and the math. You've seriously outdone yourself with this one. There's teaching math, and then there's making people absolutely love math and want to pursue it further in the future, this does the latter to such a high degree.

I solved this problem computationally. It has a very natural dynamic programming solution. The trick is to observe the following reoccurrence: numSubsets(min, max, div, mod) = numSubsets(min + 1, max, div, mod - min MOD div) + numSubsets(min + 1, max, div, mod); Basically, the number of subsets is the sum of the number of subsets using the first number plus the number of subsets not using the first number. Now just code it up, throw in the base case (if min > max, the result is 1 if the empty set works and 0 if not), and add some memoization - and you have your answer :). Use BigInteger or some equivalent to deal with integer overflow.

Art this time, and your normal visualisations seem even better Man you never stop, amazing!

Consistently blown away by this channel, thank you again for explaining something I didn't know I wanted to know.

This was really cool! I learned about the roots of unity in my engineering program, but we never saw any applications of them. They were just an exercise in complex numbers. It's cool to see how they can be useful!

18:09, Never understood complex numbers before (because I didn't care enough to really research them), this example finally clears it up for me, a group of numbers with a changing number of member numbers, imaginary numbers I at least understood to be the pair of numbers that multiply against each other to make a square but complex numbers had eluded me for a while

The cycling behaviour where things destructively interfere or constructively interfere to filter out coefficients reminds me of the Fourier transform

I am not done watching but I can tell this took a lot of effort to produce. I love your content. TY

Grant, as much as anyone, has changed how I view what education should be. And as valuable as the visuals are here, I'm sure he could do a reasonable facsimile with a whiteboard and lectern. It's all in the mystery. And yes, I'm just ripping off the points he made in his TED talk. But he sure does walk the walk.

I went from not understanding generating functions to understanding them not so long ago, and I think the way they were introduced to me was very natural. Generating functions for me started out as just a way to represent sequences of numbers which has very simple rules of addition and multiplication (just as you characterised them). It makes perfect sense if you want to evaluate the function at a point x, just the same for a polynomial. But when you consider representing combinatorial objects with generating functions, it turns out that construction of a combinatorial class using disjoint unions and cartesian products alligns beautifully with construction of generating functions using addition and multiplication. To me introducing generating functions to a combinatorial problem is something like introducing calculations with algebra to geometrical problems. It's groundbreaking and very insightful, which is why I find the title of the video to be an understatement. It's not just the olympiad level counting, it's simply the most awesome way of counting! I also appreciate the addition links. Thank you so much for the video!

I actually could follow along, the explanations where great, but the visuals are just insanely useful in understanding and even seeing what could came after. I specially liked how you insisted in those 180 rotations, when you link them to the answer for the 2 complex numbers showed in my head as the necessary next step. so nice :D

This video is absolutely beautiful. It explains all concepts clearly and I love them.

I love the roots of unity. They have a way of making things that seem difficult in their own right, very easy to solve, and also understand. It allows you to make connections between different mathematical subjects.

Your explanations are gem and should be preserved and used till end of time.

Just sent this to my former discrete math professor. I did an independent study with her on error correction codes where generating functions and roots of unity came up so I was so excited to share.

I solved this using induction of two linked series: An and Bn, where An represents the number of subsets of which the sum is divisible by 5 and Bn represents similar ones of which the remainder is 1, 2, 3 or 4. Of course, A1=8 and B1=6. We can work out: An+1=8An+24Bn and Bn+1=6An+26Bn. To check our work, we should see An+1 + 4*Bn+1 = 32*(An+4Bn). Great, as expected! Interestingly, we can notice An+1-Bn+1 = 2*(An-Bn). With these two, we can find out: An+4Bn = 32^n and An-Bn=2^n. Therefore, An = (32^n + 4*2^n) / 5. The answer of the original questions = A400. Tada :)

I'm proud to say that just when grant said what about negative 1 I immediately figured out how complex numbers come into play

I don't have enough words in my knowledge to describe how awesome math is and how it always finds ways to make me love it even more. Thank you for this gift.

I just felt down the chair listening to you. Wonderful, I never got in touch with generating function and the (generic) usefulness of the complex plane for extracting the correct coefficients of a polynomial function ... and now I have a *visual* of this all. Thanks a lot I learned a lot.

Generation function is a great and kinda magical tool. They always different, but still the same. Would be wonderfull to see more videos with them!

Always a great day when Grant uploads!

This was a fun video! Thank you again :) I've been playing around with roots of unity back at uni, and what you normally learn is the general expression z^n = 1, and then some equations so that for a given integer n you can find the solutions z. I wanted to go further, and generalized the expression to z^n = w, but I allowed both w and n to be complex numbers. The solutions z that pop out of it are absolutely beautiful, as they sit on an infinite spiral rather than a circle! I remember it as an amazing realization as I sat through the algebra during my bachelor in chemistry when I discovered this. I also haven't found any references to it on the internet. I would recommend those interested to try to sit through the algebra and come to the expressions yourself, and maybe set up some code to visualize the solutions. It's worth it!

honestly this video not only teaches math, but also teaches how to teach math. Everything you present is so elegant, every smallest detail is done with perfection which is just a cherry on top of a beautiful problem and solution you presented.

This is a trick that I've used countless times in high school math, yet I never imagined the connection between generating functions, the Riemann hypothesis and Fourier series. Truly marvellous. I also wanted to thank you. It is because of educational creators of you, that I am now in one of the premiere mathematical institutions in my country. I never even imagined that I would get selected, I only gave the exam because I find math beautiful, and you, along with many other creators, I believe, are to thank for that. Love your vids.

Your animation makes understanding these things sooo much more easier , thanks for sharing

While you can't bruteforce this, it's possible to use dynamic programming for this problem. Let's first look at the empty set {}, it has only one subset which is divisible by 5. so we have 1 subset with remainder of 0 and zero subsets with remainders of 1, 2, 3 and 4, let's write it down: (0:1, 1:0, 2:0, 3:0, 4:0) Next step we add number 1 to the set. Now we have one extra subset with remainder of 1: (0:1, 1:1, 2:0, 3:0, 4:0) What happens when we add 2? Every subset we had before will produce one extra subset by including 2 into them. So now we have one new subset with remainder of 3 and another one with remainder of 4: (0:1, 1:1, 2:1, 3:1, 4:0) And when we add 3, previous subsets with remainders of 0 will produce new ones with remainders of 3, 1 => 4, 2 => 0, 3 => 1, 4 => 2: (0:2 1:2 2:1 3:2 4:1) Similar: {+4} (0:4 1:3 2:3 3:3 4:3) {+5} (0:8 1:6 2:6 3:6 4:6) - as 5 is divisible by 5, adding it to every subset just doubles their amounts {+6} (0:14 1:14 2:12 3:12 4:12) and so on, let's code it: #!/usr/bin/python from decimal import * def solve(n): answer = [Decimal(1),Decimal(0),Decimal(0),Decimal(0),Decimal(0)] for x in range(1,n+1): r = x % 5 old_answer = answer[:] for i in range(0,5): answer[(i+r)%5] += old_answer[i] return answer a = solve(2000) print(a[0]) print((Decimal(2)**2000 + 4*Decimal(2)**400)/5) # to compare with the answer given in the video Output: 2.296261390548509048465666392E+601 2.296261390548509048465666402E+601 Sure it's not what this video is about, but maybe someone will find this useful for some reason? Also sorry for my bad english :( And thanks for this amazing video which somehow was recommended for me!

My very first thought on hearing this problem was to use Permutations and Combinations (PNC). However, I equally loved your method and was absolutely enthralled by this use of complex numbers. Thank you.

Thanks for the extra puzzles at the end! That last one stumped me for a while. I ended up stumbling on the idea of _multiplying_ by 1-x instead, and that really cracked it open for me. That, and I lost all my practice on differential equations. Took me three tries to get the right coefficients! But it was fun getting to the closed form solution.