Two sum identities.

here we're gonna look at two pretty interesting infinite sum identities so I won't give away the close form for these sums but we will be exploring the sum as K goes from zero to infinity of n choose for K and then we'll also be exploring the sum as K goes from zero to infinity

of one over three K factorial and that 3 is connected to the K so you're taking the quantity 3 K factorial and we're going to use the following combinatorial tool so if you have a 2 is equal to e to

the 2 pi over m in other words it's a primitive emp'd root of unity and a of x equals the sum as K goes from 0 to infinity of a sub K X to the K in other words it's the generating function for

the sequence a K then the sum as K goes from 0 to infinity of a MK X to the M K is equal to 1 over m times the sum as J goes from 0 to M minus 1 of a evaluated

at a de to the J times X so notice this gives us a generating function for every M terms term of the sequence so notice we start with a sub 0 the next one is a sub M then one after that is a sub 2m

and so on and so forth and so that mimics what's going on here so notice here the first one is n choose 0 then n choose 4 then n choose 8 here we have the first one is 1 over 0 factorial then 1 over 3 factorial then 1 over 6 factorial and so on and so forth so this

factorial and so on and so forth so this tool is going to be extremely helpful for finding the closed form for these sums ok so let's get to proving this tool so the first thing that I want to

notice is that a to J for J equals 0 to M minus 1 are the roots of the

polynomial Z to the M minus 1 and that's not too hard to see we can see that directly by plugging in a 2j into Z to the M minus 1 so notice we'll get a de to the

J to the M minus 1 but that's equal to e to the 2 pi I over m times J times M but now that M and the numerator and denominator will cancel and then we

denominator will cancel and then we subtract 1 but notice here we have e to the 2 pi times J times I but that's just 1 because any multiple of 2 pi I and the exponent of e you like that will give you 1 so we have 1 minus 1 which is

equal to 0 and furthermore these are all different numbers because these are all going around the unit circle in the complex plane so we have found M roots to this polynomial and since this polynomials of degree M we have all of

polynomials of degree M we have all of the roots of this polynomial great and now the next thing that we want to notice is that if you take Z to the M minus 1 we can factor a Z minus 1 out of it and when we factor a Z minus 1 out of

it we get Z to the M minus 1 plus Z to the M minus 2 all the way down plus Z plus 1 great and now notice a 2 to the 0 is equal to 1 will give you this root

right here so in other words this is the root when you set J equal to 0 and the M minus 1 roots here are given by a 2 to the 1 a 2 squared all the way up to a de to the M minus 1

great so now what we're going to do is start on the right-hand side of this equation and then we will build the left-hand side of this equation so we have 1 over m and then the sum as J goes

from 0 to M minus 1 of a evaluated at a to J times X but now using the definition that we have for a that's going to give us 1 over m and some j equals 0 to M minus 1 and then

the sum K equals 0 to infinity of a sub K times a de to the J times K times X to the K and now since this outer sum is a finite sum I can easily change the order of summation so I've got 1 over m and

of summation so I've got 1 over m and then I have the sum K equals 0 to infinity I'm going to take this a sub K term out and now I have the sum J equals 0 to M minus 1 of ADA to the JK times X

to the K okay fantastic so now we're going to split this out or sum up into two pieces the first piece will be all of the values of K that are divisible by M in other words they are multiples of them and then the second piece will be everything else so this is going to be

everything else so this is going to be equal to one over m and then we have the sum K equals zero to infinity and like I said these are going to be all of the values of K that are divisible by M in other words multiples of them so via a

quick reindex in a can write that as a sub MK and then I have the sum J equals 0 to M minus 1 of ADA to the J but then remember we've reindex k2 MK so we have