Editing Van der Waerden's theorem (section)

== Proof of Van der Waerden's theorem (in a special case) ==

The following proof is due to [[Ronald Graham|Ron Graham]], B.L. Rothschild, and [[Joel Spencer]].<ref name="Graham1990">{{cite book | last1=Graham | first1=Ronald | last2=Rothschild | first2=Bruce | last3=Spencer | first3=Joel | title=Ramsey theory | year=1990 | publisher=[[Wiley (publisher)|Wiley]] | isbn=0471500461}}</ref> [[A. Ya. Khinchin|Khinchin]]<ref>{{Harvtxt|Khinchin|1998|pp=11–17|loc=chapter 1}}</ref> gives a fairly simple proof of the theorem without estimating ''W''(''r'',&nbsp;''k'').

=== Proof in the case of ''W''(2, 3) ===
{| class="wikitable floatright" style="text-align:right
|+ ''W''(2, 3) table
! ''b'' !! colspan="5" | ''c''(''n''): color of integers
|-
! rowspan="2" | 0
| 1 || 2 || 3 || 4 || 5
|-
| &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|-
! rowspan="2" | 1
| 6 || 7 || 8 || 9 || 10
|-
| &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|-
! …
| colspan="5" | …
|-
! rowspan="2" | 64
| 321 || 322 || 323 || 324 || 325
|-
| &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|}
We will prove the special case mentioned above, that ''W''(2, 3) ≤ 325. Let ''c''(''n'') be a coloring of the integers {1, ..., 325}.  We will find three elements of {1, ..., 325} in arithmetic progression that are the same color.

Divide {1, ..., 325} into the 65 blocks {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, thus each block is of the form {5''b'' + 1, ..., 5''b'' + 5} for some ''b'' in {0, ..., 64}. Since each integer is colored either <span style="color:red;">red</span> or <span style="color:blue;">blue</span>, each block is colored in one of 32 different ways.  By the [[pigeonhole principle]], there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers ''b''<sub>1</sub> and ''b''<sub>2</sub>, both in {0,...,32}, such that

: ''c''(5''b''<sub>1</sub> + ''k'') = ''c''(5''b''<sub>2</sub> + ''k'')

for all ''k'' in {1, ..., 5}.  Among the three integers 5''b''<sub>1</sub> + 1, 5''b''<sub>1</sub> + 2, 5''b''<sub>1</sub> + 3, there must be at least two that are of the same color. (The [[pigeonhole principle]] again.)  Call these 5''b''<sub>1</sub> + ''a''<sub>1</sub> and 5''b''<sub>1</sub> + ''a''<sub>2</sub>, where the ''a''<sub>''i''</sub> are in {1,2,3} and ''a''<sub>1</sub> &lt; ''a''<sub>2</sub>.  Suppose (without loss of generality) that these two integers are both <span style="color:red;">red</span>.  (If they are both <span style="color:blue;">blue</span>, just exchange '<span style="color:red;">red</span>' and '<span style="color:blue;">blue</span>' in what follows.)

Let ''a''<sub>3</sub> = 2''a''<sub>2</sub>&nbsp;&minus;&nbsp;''a''<sub>1</sub>. If 5''b''<sub>1</sub> + ''a''<sub>3</sub> is <span style="color:red;">red</span>, then we have found our arithmetic progression: 5''b''<sub>1</sub>&nbsp;+&nbsp;''a''<sub>''i''</sub> are all <span style="color:red;">red</span>.	

Otherwise, 5''b''<sub>1</sub> + ''a''<sub>3</sub> is <span style="color:blue;">blue</span>. Since ''a''<sub>3</sub> ≤ 5,  5''b''<sub>1</sub> + ''a''<sub>3</sub> is in the ''b''<sub>1</sub> block, and since the ''b''<sub>2</sub> block is colored identically, 5''b''<sub>2</sub> + ''a''<sub>3</sub> is also <span style="color:blue;">blue</span>.

Now let ''b''<sub>3</sub> = 2''b''<sub>2</sub>&nbsp;&minus;&nbsp;''b''<sub>1</sub>. Then ''b''<sub>3</sub> ≤ 64. Consider the integer  5''b''<sub>3</sub> + ''a''<sub>3</sub>, which must be ≤ 325. What color is it?

If it is <span style="color:red;">red</span>, then 5''b''<sub>1</sub> + ''a''<sub>1</sub>, 5''b''<sub>2</sub> + ''a''<sub>2</sub>, and 5''b''<sub>3</sub> + ''a''<sub>3</sub> form a <span style="color:red;">red</span> arithmetic progression. But if it is <span style="color:blue;">blue</span>, then 5''b''<sub>1</sub> + ''a''<sub>3</sub>, 5''b''<sub>2</sub> + ''a''<sub>3</sub>, and 5''b''<sub>3</sub> + ''a''<sub>3</sub> form a <span style="color:blue;">blue</span> arithmetic progression. Either way, we are done.

=== Proof in the case of ''W''(3, 3) ===
{| class="wikitable floatright" style="text-align:right
|+ W(3, 3) table<br />''g''=2·3<sup>7·(2·3<sup>7</sup>&nbsp;+&nbsp;1)</sup>&nbsp;,<br />''m''=7(2·3<sup>7</sup>&nbsp;+&nbsp;1)
! ''b'' !! colspan="5" | ''c''(''n''): color of integers
|-
! rowspan="2" | 0
| 1 || 2 || 3 || … || ''m''
|-
| &nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || … || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp;
|-
! rowspan="2" | 1
| ''m'' + 1 || ''m'' + 2 || ''m'' + 3 || … || 2''m''
|-
| &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp; || … || &nbsp;'''<span style="color:red;">R</span>'''&nbsp;
|-
! …
| colspan="5" | …
|-
! rowspan="2" | ''g''
| ''gm'' + 1 || ''gm'' + 2 || ''gm'' + 3 || … || (''g'' + 1)''m''
|-
| &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || &nbsp;'''<span style="color:red;">R</span>'''&nbsp; || &nbsp;'''<span style="color:blue;">B</span>'''&nbsp; || … || &nbsp;'''<span style="color:limegreen;">G</span>'''&nbsp;
|}
A similar argument can be advanced to show that ''W''(3, 3) ≤ 7(2·3<sup>7</sup>+1)(2·3<sup>7·(2·3<sup>7</sup>+1)</sup>+1). One begins by dividing the integers into  2·3<sup>7·(2·3<sup>7</sup>&nbsp;+&nbsp;1)</sup>&nbsp;+&nbsp;1 groups of 7(2·3<sup>7</sup>&nbsp;+&nbsp;1) integers each; of the first 3<sup>7·(2·3<sup>7</sup>&nbsp;+&nbsp;1)</sup>&nbsp;+&nbsp;1 groups, two must be colored identically.

Divide each of these two groups into 2·3<sup>7</sup>+1 subgroups of 7 integers each; of the first 3<sup>7</sup>&nbsp;+&nbsp;1 subgroups in each group, two of the subgroups must be colored identically.  Within each of these identical subgroups, two of the first four integers must be the same color, say <span style="color:red;">red</span>; this implies either a <span style="color:red;">red</span> progression or an element of a different color, say <span style="color:blue;">blue</span>, in the same subgroup.

Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either <span style="color:red;">red</span> or <span style="color:blue;">blue</span>, would complete a <span style="color:red;">red</span> or <span style="color:blue;">blue</span> progression, by a construction analogous to the one for ''W''(2, 3). Suppose that this element is <span style="color:limegreen;">green</span>. Since there is a group that is colored identically, it must contain copies of the <span style="color:red;">red</span>, <span style="color:blue;">blue</span>, and <span style="color:limegreen;">green</span> elements we have identified; we can now find a pair of <span style="color:red;">red</span> elements, a pair of <span style="color:blue;">blue</span> elements, and a pair of <span style="color:limegreen;">green</span> elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.

=== Proof in general case ===
The proof for ''W''(2, 3) depends essentially on proving that ''W''(32, 2) ≤ 33.  We divide the integers {1,...,325} into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block colored the opposite way.  Similarly, the proof for ''W''(3, 3) depends on proving that

: <math>W(3^{7(2 \cdot 3^7+1)},2) \leq 3^{7(2 \cdot 3^7+1)}+1.</math>

By a double [[mathematical induction|induction]] on the number of colors and the length of the progression, the theorem is proved in general.