# pigeonhole what are the parts of the proof using the pigeonhole principle?

We can divide a proof by induction in two parts: Inductive base and Inductive step. One proves for the case when n = 1, and after one suppouse what we want to prove is the case for an arbitrary k, then we prove k+1 is also true.

Now, I want to know the parts of the pigeonhole principle. When I want to prove something using the pigeonhole principle what I must to do?. An example will make it clear, say this problem In the problem assume that n is a natural number greater or equal to 2 and even.

How can I solve it using the pigeonhole principle, more concret, what are the parts of the proof using the pigeonhole principle?

• I'm assuming, $n\in\mathbb N$, where $n\geq 2$? Oct 4, 2021 at 1:10
• Yes Owen, I forgot it Oct 4, 2021 at 1:13
• Note for $n=2$, set up your pigeonholes and prove the trivial case. Then suppose for some $n\in\mathbb N$ that it holds with your associated pigeonholes. Then show for $n +1$. Also note that for $n=2$, one could easily do brute force, but setting up your pigeonholes first allows you to easily extend to $n\in\mathbb N$. Oct 4, 2021 at 1:14
• Please do not use images, especially for such small piece of text. See here why images should not be used to convey key information. Oct 4, 2021 at 1:22
• @Ratamágica, also, I feel like it should also say that $n$ should be even. Consider $n=5 \implies \frac 52 +1 = 2.5 + 1 = 3.5$. Picking 3.5 elements from the set doesn't make sense. Oct 4, 2021 at 1:24

Direct approach that does not use induction.

Assume that the selected (distinct) numbers, in ascending order are

$$A = \{a_1, a_2, \cdots, a_{(n/2) + 1}\}.$$

For $$k \in \{1,2, \cdots, [(n/2) + 1]\},~$$ let $$b_k = (n+1) - a_k$$.

Let $$B = \{b_1, b_2, \cdots, b_{(n/2) + 1}\}.$$

As defined, $$B \subseteq \{1,2,\cdots, n\}.$$

Note that the set $$\{1,2,\cdots, n\}$$ only has $$(n)$$ elements, while the sets $$A$$ and $$B$$ each have [(n/2) + 1] distinct elements from $$\{1,2,\cdots,n\}$$. Therefore, by the pigeonhole principle, there must be an element $$b_r \in B$$ that equals some element $$a_s \in A$$.

Therefore, $$a_r + a_s = (n+1).$$

Note that since $$n$$ even, $$(n+1)$$ is odd.
Therefore, $$a_r, a_s$$ must be two distinct elements (else their sum would be even).