Question

I seem to have the right idea here, but have a little trouble following through with it.

Answer 1

So here's the original problem:\[\binom{n}{3} + \binom{n}{7} + \binom{n}{11}+ \cdots \]

Answer 2

Now here's what I thought: I should plug something in which has its powers repeating periodically with a period of four. Oh hey, why not the fourth roots of unity?

Answer 3

So I decided to get on with it! Yeaaaah!

The fourth roots of unity, as we know them, are \(1\), \(-1\), \(i\) and \(-i\). If we plug them in to the expression for \((1+x)^n\) and kinda mess around with the thing... maybe adding and subtracting... we'll get the answer.

Answer 4

I'll denote \(\binom{n}{r}\) as \(C_r\) for short.\[(1+i)^n = C_0 + iC_1 - C_2 - iC_3 + \cdots \]\[(1-i)^n =C_0 -iC_1 - C_2 + iC_3 + \cdots \]\[(1-1)^n = C_0 - C_1 + C_2 - C_3 + \cdots \]\[(1+1)^n = C_0 + C_1 + C_2 + C_3 + \cdots \]Kinda thinking of it in terms of constructive and destructive interference.

Answer 5

you're on the right track. this is basically the same thing you use when defining even and odd parts of a function \(f\) as follows: $$f_e(x)=\frac12(f(x)+f(-x))\\f_o(x)=\frac12(f(x)-f(-x))\\f(x)=f_e(x)+f_o(x)=\frac12(2\cdot f(x))=f(x)$$

Answer 6

except now instead of looking at mere even, odd terms, we're doing a more general discrete fourier transform to extract the terms corresponding to a different period; the generalization is from \((\pm1)^2=1\) to roots of unity as you noted \((e^{2\pi ik/n})^n=1\) for \(k\in\{0,1,2,\dots,n-1\}\)

Answer 7

Now\[\frac{(1-i)^n - (1+i)^n}2 = -iC_1 + i C_3 -iC_5 + \cdots \]And\[i\frac{(1+1)^n - (1-1)^n}{2}=iC_1 + iC_3 + iC_5 + \cdots \]I add both and it's done, I guess.

Answer 8

so just like we define \(\cosh x\) and \(\sinh x\) as the even and odd parts of \(e^x\): $$\cosh x=\frac12(e^x+e^{-x})\\\sinh x=\frac12(e^x-e^{-x})$$or, likewise, \(\cos x,\sin x\) as something *like* the even and odd parts of \(e^{ix}\): $$\cos x=\frac12(e^{ix}+e^{-ix})\\\sin x=\frac1{2i}(e^{ix}-e^{-ix})$$

Answer 9

Oh, yeah. That totally makes sense. Nice.

Answer 10

in this case, notice the binomial theorem tells us: $$(1+x)^n=\sum_{k=0}^n\binom{n}k x^k$$
if we use \(x=e^{2\pi i/4}\), so that \(x=i,x^2=-1,x^3=-i,x^4=i\) we see: $$(1+i)^n=\sum_{k=0}^n\binom{n}k i^{k}=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\binom{n}{2k}+i\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\binom{n}{2k+1}$$and similarly $$(1-i)^n=\sum_{k=0}^n(-1)^k\binom{n}k i^k=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^{k}\binom{n}{2k}-i\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\binom{n}{2k+1}\\(1+1)^n=\sum_{k=0}^n\binom{n}k\\(1-1)^n=\sum_{k=0}^n(-1)^k\binom{n}k$$so observe that \(\frac1{2i}\left[(1+i)^n-(1-i)^n\right]\) annihilates the even terms and gives alternating odd terms, while \(\frac12\left[(1+1)^n-(1-1)^n\right]\) annihilates even terms and gives non-alternating odd terms, and combining these to give: $$\frac14\left[{(1+1)^n+(1+i)^n-(1-1)^n-(1-i)^n}\right]=\sum_{k=0}^{\lfloor n/3\rfloor}\binom{n}{4k+3}$$

Answer 11

Oh boy, you didn't need to write all that.

Answer 12

oops, forgot some \(i\)s in the final expression, but that's besides the point :-p

Answer 13

I'm already done with the problem - and thank you for providing that analogy and insight. :)

Answer 14

$$\frac14\left[(1+1)^n-i(1+i)^n-(1-1)^n+i(1-i)^n\right]$$
and note for \(f(x)=(1+x)^n\) this is precisely $$\frac14\sum_{k=0}^4 f(e^{2\pi ik/4})\cdot e^{-2\pi ik/4}$$