An arithmetic sequence of step $d$ is a set of the form:
{$a, a+d, a+2d, a+3d, …$} where $a, d$ are positive integers.
Show that the positive integers cannot be partitioned into a finite number of arithmetic sequences s.t. each sequence has a distinct step $d$. (Except the trivial sequence $a=1, d=1$.)
Now the book gives me a hint:
Write $\sum_{n\in\mathbb{N}}z^n$ as a sum of terms of the type $\frac{z^a}{1-z^d}$.
But it isn't clear that the power series can even be put such a form, and even if it can, why does that help me?
Best Answer
This is a pretty problem. I asked a question about it in MathOverflow a while back. Here is the solution using complex analysis, copying from the link above, and adding some details: (I've added the details in between square brackets. Ignore those paragraphs if you want to work out the details on your own.)
Assign to each progression $A_i=(a_i+kb_i\mid k\in{\mathbb N})$, $1\le i\le n$, its generating series, $f_i(x)=\sum_{k=0}^\infty x^{a_i+kb_i}$. Then $f_i(x)=x^{a_i}/(1-x^{b_i})$. Note the series converges for $|x|<1$.
[ To see this: $\sum_{k=0}^\infty x^{a_i+kb_i}=x^{a_i}\sum_{k=0}^\infty (x^{b_i})^k$, and use that if $|t|<1$, the geometric series $\sum_{k=0}^\infty t^k$ equals $1/(1-t)$. ]
Now, since the $A_i$ partition ${\mathbb N}$, we have $\sum_{i=1}^n f_i(x)=\sum_{m=1}^\infty x^m=x/(1-x)$.
[ For this, observe that if $m\in A_i$, then $x^m$ is one of the terms being added in $f_i(x)$, and $x^m$ is not a term in any of the other series $f_j$ for $j\ne i$. ]
If all the $b_i$ are different, let $b$ be the largest, and fix a primitive $b$-th root of unity $\zeta$. Now let $x\to\zeta$ to reach a contradiction.
[ In detail, $\zeta=e^{2\pi i/b}$ is a primitive $b$-th root of unity ($i$ the square root of $-1$). This means that $\zeta^b=1$, if $k$ is an integer, then $\zeta^k=1$ iff $k$ is a multiple of $b$, and if $z^b=1$, then $z=\zeta^n$ for some integer $n$. You then have that $$\frac{x^{a_1}}{1-x^{b_1}}+\dots+\frac{x^{a_n}}{1-x^{b_n}}=f_1(x)+f_2(x)+\dots f_n(x)=\sum x^m=\frac x{1-x}. $$ Call $(*)$ this equation. When $x\to\zeta$, we obtain on the right hand side of $(*)$ the fraction $\displaystyle \frac{\zeta}{1-\zeta}$. Note here that $\zeta\ne 1$ because we are assuming we have at least two arithmetic progressions, so $b>1$. On the other hand, if $b_j\ne b$, then $$ \frac{x^{a_j}}{1-x^{b_j}}\to\frac{\zeta^{a_j}}{1-\zeta^{b_j}} $$ and $\zeta^{b_j}\ne 1$ because $b>b_j$. But if $b_j=b$, then $\displaystyle \frac{x^{a_j}}{1-x^{b_j}}\to\infty$ because $\zeta^{b_j}=\zeta^b=1$. The contradiction is that the left hand side of $(*)$ converges to $\infty$, while the right hand side does not. ]
This shows that the largest of the common differences must appear at least twice.
As Gerry Myerson pointed out in MO, this argument is due to D J Newman. It appears in his book A Problem Seminar, problem 90, on page 18, with solution on page 100.