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?
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).