<s>[INST] 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.
 [/INST] Here are two examples which might be useful

  
*
  
*Example 1: Generalize in order to use techniques from analysis resp. formal operator techniques

Problem: Evaluate
$$\sum_{k=1}^{n}\frac{k^2}{2^k}$$

This can be done by instead evaluating
$$\sum_{k=1}^{n}k^2x^k$$
For $x\neq 1$ we know that
$$S(x)=\sum_{k=1}^{n}x^k=\frac{1-x^{n+1 }}{1-x}$$
Now differentiating each side and multiplying with $x$ we get
\begin{align*}
(xD)S(x)&=\sum_{k=1}^{n}kx^{k}\\
&=(xD)\frac{1-x^{n+1 }}{1-x}\\
&=\left(1-(n+1)x^n+nx^{n+1}\right)\frac{x}{\left(1-x\right)^2}
\end{align*}
Differentiating again each side and multiplying with $x$ we get
\begin{align*}
{(xD)}^2S(x)&=\sum_{k=1}^{n}k^2x^{k}\\
&=(xD)^2\frac{1-x^{n+1 }}{1-x}\\
&=\left(1+x-(n+1)^2x^n-(2n^2+2n-1)x^{n+1}-n^2x^{n+2}\right)\frac{x}{\left(1-x\right)^3}
\end{align*}

We conclude

\begin{align*}
S\left(\frac{1}{2}\right)&=\sum_{k=1}^{n}\frac{k^2}{2^k}\\
&=\left(\frac{3}{2}-(n+1)^2\frac{1}{2^n}-(2n^2+2n-1)\frac{1}{2^{n+1}}-n^2\frac{1}{n+2}\right)\cdot 4\\
&=6-\frac{1}{2^n}\left(n^2+4n+6\right)
\end{align*}


Another example where generalization is useful

  
*
  
*Example 2: Generalize integrals by introducing a parameter and use the technique of parameter differentiation

Problem: Evaluate
$$\int_{0}^{\infty}\frac{\sin^2 x}{x^2}dx$$
given that $\int_{0}^{\infty}\frac{\sin x}{x}dx=\frac{1}{2}\pi$.

The idea is to introduce a parameter and evaluate the more general integral
\begin{align*}
I(a)=\int_{0}^{\infty}\frac{\sin^2 (ax)}{x^2}dx,\qquad a\geq 0\tag{1}
\end{align*}
and use parameter differentiation.
Differentiating each side of (1) with respect to $a$, we get
\begin{align*}
I^{\prime}(a)&=\int_{0}^{\infty}\frac{2\sin (ax)\cos (ax)\cdot x}{x^2}dx\\
&=\int_{0}^{\infty}\frac{2\sin (2ax)}{x}dx\\
\end{align*}
  Now substituting $y=2ax$, we get $dy = 2a dx$, and
  \begin{align*}
I^{\prime}(a)&=\int_{0}^{\infty}\frac{\sin y}{y}dx=\frac{1}{2}\pi\\
\end{align*}
Integrating each side gives
$$I(a) =\frac{1}{2}\pi a+C,\qquad C \text{ constant}$$

Since $I(0)=0$, we get $C=0$. Thus $I(a)=\frac{1}{2}\pi a, a\geq 0$. Setting $a=1$ yields
$$I(1)= \int_{0}^{\infty}\frac{\sin ^2 x}{x^2}dx = \frac{1}{2}\pi$$

Note: The examples above can be found in Problem-Solving Through Problems. They are stated as problems 1.12.1 and 1.12.3 in chapter 1.12 Generalize.
</s>