mathematical methods, heuristics, principles

Induction (under construction)
induction by the method of undetermined coefficients
Name and conquer
completing the square – see e.g. the quadratic formula
perturbation
If you have a transformation, look for an invariant!
Pigeonhole principle

Show that in any group of people, at least 2 will each know the same number of people.
Solution. With n people, label them according to how many they know. This will range from 0 to n-1. But If someone knows no-one (label 0), no-one knows n-1. By the pigeonhole principle, there are n people with n-1 labels, and at least 2 must know the same number of people.

Extremal principle: Pick an object which maximizes/minimizes some function.

Every member of Parliament has three enemies at most in the parliament. Show that one can divide the house into two groups so that every member has at most one enemy in his house.
Solution: Consider all partitions of the Parliament into two houses and, for each partition, count the total number E of enemies each member has in his house. The partition with minimal E has the required property. If some member had two or more enemies in his house, then he would have one enemy at most in the other house. By placing him in the other house, we could decrease the minimal E, which is a contradiction.

divisibility

$a-b|a^n-b^n$
$a+b|a^n+b^n$ (for odd $n$ .
Sophie Germain’s identity: $a^4+4b^4=(a^2+2b^2+2ab)(a^2+2b^2-2ab)$

Common Identities

Lagrange’s identity: $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$ .

Let $m$ and $n$ be distinct positive integers. Represent $m^6+n^6$ as the sum of two perfect squares different from $m^6$ and $n^6$ .
Solution: $m^6+n^6=(m^2)^3+(n^2)^3$
~~+++++++~~ $=(m^2+n^2)(m^4-m^2n^2+n^4)$
~~+++++++~~ $=(m^2+n^2)((m^2-n^2)^2+(mn)^2)$
Substituting in $a=m$ , $b=n$ , $c=m^2-n^2$ and $d=-mn$ :
~~+++++++~~ $m^6+n^6=(m^3-2mn^2)^2+(n^3-2m^2n)^2$ .

Catalan’s identity

$1-\fr{2}+\fr{3}-\fr{4}+\cdots+\fr{2n-1}-\fr{2n}=\fr{n+1}+\fr{n+2}+\cdots+\fr{2n}.$

Proof: Set $S_k=1+\fr{2}+\cdots+\fr{k}$ ~~++++~~ $(k=1,2,\dots).$ Then :

$\begin{align*} 1-\fr{2}+\fr{3}-\fr{4}+\cdots+\fr{2n-1}-\fr{2n} &= S_{2n}-2(\fr{2}+\fr{4}+\cdots+\fr{2n}) \\ &= S_{2n}-S_n \\ &= \fr{n+1}+\fr{n+2}+\cdots+\fr{2n}. \end{align*}$

Search for a pattern.
Draw a figure.
Formulate an equivalent problem.
Modify the problem.

Choose effective notation.
Exploit symmetry.
Divide into cases.
Work backward.
Argue by contradiction.
Pursue parity.

Q. In how many ways can you enter through one door, pass through every room exactly once, and go out the other door?

A. None. With this chess-board colouring, the 2nd, 4th and every even-numbered room visited is white. But there are an even number of rooms, and the last room on such a path would be even and black.

Generalize.

sources

Loren C Larson – Problem-solving through problems (1983)
Arthur Engel – Problem-solving Strategies (2008)