Examples where it is easier to prove more than less

Especially (but not only) in the case of induction proofs, it happens that a stronger claim $B$ is easier to prove than the intended claim $A$ (e.g. since the induction hypothesis gives you more information). I am trying to come up with exercises for beginner students that help to demonstrate this point (and also interested in the general phenomenon). Do you know any good examples (preferably elementary ones) where strengthening a claim makes the proof easier?

Here is an example of what I mean (Problem 16 from chapter 7 of Engel's `Problem solving strategies'):

Show that $\frac{1}{2}\frac{3}{4}...\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n}}$ for $n\geq 1$. This is much harder than proving the stronger statement that $\frac{1}{2}\frac{3}{4}...\frac{2n-1}{2n}\leq\frac{1}{\sqrt{3n+1}}$ for $n\geq 1$, which is a straightforward induction.

Here's my favorite proof - for the reasons that it's very easy and elementary enough that it takes almost no mathematical knowledge at all - for an example of the general case that is easier than the special case:

Problem: For every $2^n\times2^n$ grid where $n$ is a natural number, there is a covering with $L$ shaped pieces, all have an area of $3$ squares, that leaves one central square (one of four central squares) empty.

Here is an example for $n=2$:

General case is:

Problem: For every $2^n\times2^n$ grid where $n$ is a natural number, there is a covering with $L$ shaped pieces, all have an area of $3$ squares, that leaves only one arbitrarily specified square empty.

General case claims that we can choose any square (not necessarily center as opposed to special case) we want to be empty, before covering. Proof is very easy and uses induction on $n$:

Let $P(n)$ be the proposition that problem states.

Base case: $P(0)$ is obvious.

Inductive step: Assume $P(n)$ for some $n\in\mathbb{N}$. Take any $2^{n+1}\times2^{n+1}$ board and arbitrarily choose one square which will be empty. Divide the board four $2^n\times2^n$ quadrants. From hypothesis; there is a covering of the quadrant which has chosen square on it, and covering of all other quadrants except three center squares of the big square like this:

Here, red is chosen square and blues are empty squares for other quadrants. Now, put one piece on blue squares and you have $P(n+1)$. $\blacksquare$

For me; this argument is also very effective way to make people, who have little or no mathematical experience, to comprehend that sometimes why and how proving general case may be easier than special one. Therefore make an excellent example to demonstrate this point for beginner students.

Here's my favorite. Let $(a,n)=1$. Then there are infinitely many primes $p \equiv a \pmod{n}$, and with analytic density $\frac{1}{\phi(n)}$. This is easier to prove (in general) than just showing a single prime $p \equiv a \pmod{n}$ exists, since as far as I know there is no general way to just find a single one without just finding them all with the proper density. If you go looking for just a single one you'll probably get stuck.

Here is a relevant (albeit somewhat simplistic) example from the representation theory of finite groups.

An orbit of a finite group $G$ on a finite vector space $V$ is a set $v^G=\{v^g:g\in G\}$. (Here, I'm using "group theorist notation," where $v^g$ denotes $g$ acting on $v$. It's what you usually see written as $v\cdot g$ or $g\cdot v$ in algebra textbooks.) A regular orbit on $V$ is an orbit such that $\left|v^G\right|=\left|G\right|$. So, by Orbit-Stabilizer, we have that $\left[G:\operatorname{Stab}_G(v)\right]=\left|G\right|$, which means that $\operatorname{Stab}_G(v)=1$. Saying that $G$ has a regular orbit on $V$ is, therefore, equivalent to finding some element of $V$ that is fixed only by the identity. Determining when groups have regular orbits is a well-studied problem in group theory, about which there are many open conjectures.

One would think that it would be easier to find one regular orbit on $V$ than to count all the not-regular orbits instead. However, in practice, we often find ourselves showing that $$\left|\bigcup_{1\ne g\in G}\mathbf{C}_V(g)\right|< \left|V\right|$$ So, we're saying, "Look at all these vectors that aren't part of regular orbits! As you can see, there's still room left in $V$, so the remaining orbits must be regular."

To deal with the left hand side, we must explicitly compute all these fixed point sets, determine their intersections, apply inclusion-exclusion, and so on. What we get is much more information about the group than the regular orbit we originally sought for, but in many cases, a simpler method is not known.