If a_n>a_(n+1)>0 for all sufficiently large n, prove that
If $a_n>a_{n+1}>0$ for all sufficiently large $n$, prove that the series $\sum_{n=1}^{\infty} a_n$ and the series $\sum_{n=1}^{\infty} 2^n a_{2^n}$ converge or diverge simultaneously.
Explanation of Method
Grouping the terms of $\sum a_n$ into dyadic blocks $[2^k,2^{k+1})$ and using monotonicity to bound every term in a block between the block's two endpoint values produces a two-sided sandwich: the condensed sum $\sum2^ka_{2^k}$ controls the original partial sums from above, and (up to a factor of $2$) from below as well. This sandwich forces the two series to share the same convergence behavior.
- Group the partial sums of $\sum a_n$ by dyadic blocks $[2^k,2^{k+1})$.
- Bound each block above and below using monotonicity, to relate $S_N$ and $T_m=\sum2^ka_{2^k}$.
- Conclude both directions of the equivalence from the resulting two-sided inequality.
Step 1 · Group by dyadic blocks
Assume $a_n$ is decreasing for all $n\ge1$. For $2^m\le N<2^{m+1}$, group $S_N=\sum_{n=1}^Na_n$ into blocks $[2^k,2^{k+1})$, each containing $2^k$ terms.
Step 2 · Bound each block
Since $a_n$ is decreasing, every term in $[2^k,2^{k+1})$ is at most $a_{2^k}$ and at least $a_{2^{k+1}-1}\ge a_{2^{k+1}}$:
$$ 2^k a_{2^{k+1}} \le \sum_{n=2^k}^{2^{k+1}-1} a_n \le 2^k a_{2^k}. $$
Summing the upper bound over $k=1,\ldots,m$: $S_N\le a_1+\sum_{k=1}^m2^ka_{2^k}$. Summing (a rescaled version of) the lower bound: $\sum_{k=1}^m2^ka_{2^k}\le2\sum_{n=1}^{2^m}a_n$.
Step 3 · Combine into the sandwich and conclude
$$ \frac12\sum_{k=1}^m 2^k a_{2^k} \;\le\; \sum_{n=1}^{2^m} a_n \;\le\; a_1 + \sum_{k=1}^m 2^k a_{2^k}. $$
If $\sum2^ka_{2^k}$ converges, the right inequality bounds $S_N$, so $\sum a_n$ converges (increasing, bounded partial sums). If $\sum a_n$ converges, the left inequality bounds $T_m$, so $\sum2^ka_{2^k}$ converges. By contrapositive, divergence of either forces divergence of the other.
Summary Table
| Direction | Mechanism |
|---|---|
| $\sum2^ka_{2^k}$ converges $\Rightarrow\sum a_n$ converges | Upper bound: $S_N\le a_1+T_m$ |
| $\sum a_n$ converges $\Rightarrow\sum2^ka_{2^k}$ converges | Lower bound: $T_m\le2S_{2^m}$ |
Additional Notes
- Applying this test to $a_n=\frac1{n^\alpha}$ gives $2^na_{2^n}=2^{n(1-\alpha)}$, a geometric series converging iff $1-\alpha<0$, i.e. $\alpha>1$ — instantly recovering Problem 94's $p$-series threshold without any integral computation.
- Applied to $a_n=\frac1{n(\ln n)^\alpha}$ (Problem 95), condensation gives $2^na_{2^n}=\frac1{(n\ln2)^\alpha}$, again a $p$-series in $n$ with the same threshold $\alpha>1$ — condensation converts an awkward logarithmic series into a plain power series almost for free.
- Cauchy's condensation test is essentially a discrete cousin of the integral test: instead of comparing $\sum a_n$ to $\int f(x)dx$, it compares $\sum a_n$ to a geometrically-sparser sum $\sum2^ka_{2^k}$, and both techniques rely fundamentally on the monotonicity of the underlying sequence or function.
Result
The two series always converge or diverge together: