Mathematical induction and pigeon-hole principle

Question

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2.

In my attempt.

I try $n=2$, and so we have $\{1,2,3,4\}$ and we could partition $\{1,2,3,4\}$ into two boxes with $2$ numbers in each as follows $\{1,3 \}$ and $ \{2,4 \}$. Now these two boxes are my pigeon-holes and I want to take $n+1=3$ numbers from these two boxes and so by the pigeon-hole principle, I have to take one of the two boxes that have two integers that differ by 2 and hence done.

Now I want to generalise this for any $n=2k$, How can I do it.

I thought about proceeding by induction.

Assume this works for $n=2k$ now I want to show that it works for $n=2(k+1)$.

Assume that it works for $\{1,2,.....,4k \}$, I want to show that it works for $\{1,2,.....,4k + 4 \}$

So because it works for $$\{1,2,.....,4k \}$$

This means that if $n+1 = 2k +1$ integers are chosen from

$$\{1,2,.....,4k \}$$

then there are always two integers that differ by 2.

Now considering $\{1,2,.....,4k + 4 \}$

The difference between $\{1,2,.....,4k + 4\}$ and $\{1,2,.....,4k \}$

Is just 4 numbers $$ \{4k+1,4k+2,4k+3,4k+4 \}$$

Now if we want to choose $n+1 = 2k +3$. Then I stop here, And don't know how to proceed .

Any suggestions ? or is there another way to answer this question without mathematical induction !

Answer 1

Divide the $4k+4$ numbers into group A = $\{1,...,4k\}$ and group B=$\{4k+1,...,4k+4\}$. I want to pick as many numbers as possible without any two numbers that differ by $2$.
You have shown that I can pick at most two from group B. It's the same argument as your main paragraph.
By the inductive hypothesis, I can pick at most $2k$ from group A.
So altogether I can pick at most $2k+2$ numbers without two that differ by $2$.
In other words, if I pick $2k+3$, I will have two that differ by $2$.

Answer 2

Your induction proof can be made simpler. You already proved the base case. Now suppose you choose $m+1$ numbers from a set of size $2m$ where $m=n+2$. Let $s$ be the smallest number chosen. If $s+2$ has also been chosen you are done. If not, consider the set $\{s+k, ...,2m\}$ where $k=1$ or $k=2$, whichever makes the set have even cardinality. Since this is less than or equal to $2n$, by the induction hypothesis, there must be two numbers that are two apart.