|
|
本帖最后由 hbghlyj 于 2023-7-4 23:16 编辑 summation.pdf page 6:
A classic MathCounts-flavored problem goes as follows: we wish to compute
$$
\sum_{k \geq 0}\left(\begin{array}{c}
1000 \\
2 k
\end{array}\right)
$$
In order to do this, we use the fact that
$$
\begin{aligned}
&(1+1)^{1000}=\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) \\
&(1-1)^{1000}=\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right)(-1)^{n}
\end{aligned}
$$
Adding these together, we get that twice the desired sum is $2^{1000}$ hence the answer is $2^{999}$. The key fact we used was that
$$
\frac{1^{n}+(-1)^{n}}{2}= \begin{cases}1 & n \text { even } \\ 0 & n \text { odd }\end{cases}
$$
This trick can be generalized using a so-called roots of unity filter. To motivate it, we consider the following example problem.
Example 2.6 (Classical application of roots of unity filter) Compute
$$
\sum_{k \geq 0}\left(\begin{array}{c}
1000 \\
3 k
\end{array}\right)
$$ |
Solution. We can rewrite the sum as
$$
\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) f(n)
$$
where
$$
f(n)= \begin{cases}1 & n \equiv 0 \quad(\bmod 3) \\ 0 & \text { otherwise. }\end{cases}
$$
So we want the mod 3 analog of the parity detector $1^{n}+(-1)^{n}$ we had earlier. The trick, which gives it the name "roots of unity filter", is that we can take
$$
f(n)=\frac{1}{3}\left(1^{n}+\omega^{n}+\omega^{2 n}\right)
$$
where $\omega=\exp \left(\frac{2}{3} \pi i\right)$ is a cube root of unity, satisfying the relation $\omega^{2}+\omega+1=0$. Thus, we have
$$
\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) f(n)=\frac{1}{3} \sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right)\left(1+\omega^{n}+\omega^{2 n}\right)
$$
We can swap the order of summation now (never gets old, does it?) and instead consider
$$
\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) f(n)=\frac{1}{3} \sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right)+\frac{1}{3} \sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) \omega^{n}+\frac{1}{3} \sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) \omega^{2 n}
$$
(This doesn't look like the previous examples of swapping the order of summation, but perhaps I could instead write $\sum_{n \geq 0} \sum_{k=0}^{2}\left(\begin{array}{c}1000 \\ n\end{array}\right) \omega^{n k}=\sum_{k=0}^{2} \sum_{n \geq 0}\left(\begin{array}{c}1000 \\ n\end{array}\right) \omega^{n k}$. The point is we are exchanging an $1000 \times \overline{3}$ sum with a $3 \times 1000$ sum.) Thus by the binomial theorem the expression in question is
$$
\begin{aligned}
\sum_{n \geq 0}\left(\begin{array}{c}
1000 \\
n
\end{array}\right) f(n) &=\frac{1}{3}\left[(1+1)^{1000}+(1+\omega)^{1000}+\left(1+\omega^{2}\right)^{1000}\right] \\
&=\frac{1}{3}\left[2^{1000}+\left(-\omega^{2}\right)^{1000}+(-\omega)^{1000}\right] \\
&=\frac{1}{3}\left[2^{1000}+\omega+\omega^{2}\right] \\
&=\frac{1}{3}\left[2^{1000}-1\right] .
\end{aligned}
$$$\square$
§2.4 Problems
Problem 2.7 (Putnam 2011). Let $a_{1}, a_{2}, \ldots$ and $b_{1}, b_{2}, \ldots$ be sequences of positive real numbers such that $a_{1}=b_{1}=1$ and $b_{n}=b_{n-1} a_{n}-2$ for $n=2,3, \ldots$. Assume that the sequence $\left(b_{j}\right)$ is bounded. Prove that
$$
S=\sum_{n=1}^{\infty} \frac{1}{a_{1} \cdots a_{n}}
$$
converges, and evaluate $S$.
Problem 2.8 (Putnam 2013). Let $a_{0}, a_{1}, \ldots, a_{n}, x$ be real numbers, where $0<x<1$, satisfying
$$
\frac{a_{0}}{1-x}+\frac{a_{1}}{1-x^{2}}+\cdots+\frac{a_{n}}{1-x^{n+1}}=0
$$
Prove that for some $0<y<1$ we have
$$
a_{0}+a_{1} y+a_{2} y^{2}+\cdots+a_{n} y^{n}=0 .
$$
Problem 2.9 (Putnam 2015). Let $T$ be the set of triples of positive integers whose lengths are the sides of a triangle. Compute
$$
\sum_{(a, b, c) \in T} \frac{2^{a}}{3^{b} 5^{c}}
$$
Problem 2.10. How many nonempty subsets of $\{1,2, \ldots, 1000\}$ have sum divisible by 3 ? |
|
