CommeUnJeu · L1 PCSI

Reasoning and writing mathematics

⌚ ~115 min ▢ 14 blocks ✓ 53 exercises ➣ Prerequisites : Logic

Chapter overview

This chapter is the toolbox of mathematical writing for this course. It does not introduce new mathematical objects: instead, it codifies the writing patterns a mathematician uses again and again --- how to introduce an object, how to prove a universal or existential statement, how to write an induction, how to argue by contradiction, how to handle the analysis-synthesis device, how to define a function correctly.
In the final year of high school, the chapter Reasoning and Proof already presented the four-step structure of a written proof --- Statement, Assumptions, Logical Steps, Conclusion. This chapter refines each of those steps at this level: vocabulary precision (axiom, definition, theorem, proposition, lemma, corollary, characterization), verb-grammar (Let vs Set vs Denote by), explicit universal/existential/uniqueness templates, the discipline of the implication arrow ($\Rightarrow$ is not the word therefore), double and strong induction, the analysis-synthesis device, and clean writing with functions.
Each section follows the same micro-rhythm: a Text block introduces the pattern, a Method block presents the writing template in skeleton form, and one or two Examples apply the template on a small concrete problem. A few sections close with an Attention Text block isolating a common mistake. Throughout this chapter, $\mathbb{K}$ denotes $\mathbb{R}$ or $\mathbb{C}$, $\mathbb{N}^*$ denotes $\mathbb{N} \setminus \{0\}$, and $\mathbb{R}_+$ denotes the set of non-negative real numbers.

I Vocabulary: axioms$\virgule$ definitions$\virgule$ theorems

Why vocabulary matters

Mathematics builds a tower of true statements starting from a small base of accepted truths and following strict rules of derivation. The vocabulary distinguishes the bottom (axioms, accepted), the middle (definitions, naming conventions), and the top (theorems, derived). Within the « derived » floor, four words refine the role of a statement: proposition, lemma, corollary, characterization. Knowing which word to use is not pedantry --- it tells the reader at a glance what role the statement plays in the chapter.

Definition — Axiom

An axiom is a proposition accepted as true without justification, taken as a starting point of a theory. In this course, we admit the existence of $\mathbb{R}$ with all the properties of the real numbers learned in the final year of high school, rather than constructing $\mathbb{R}$ from more elementary axioms.

Definition — Definition

A definition introduces a word or a symbol by specifying its exact mathematical meaning. It may name an object, a class of objects, a property, a relation, or an operation. Within a given active scope of reasoning, the same symbol must not have two meanings.

Definition — Theorem and its variants

A theorem is a proposition derived from axioms, definitions, and previously established results. Four refinements name the role a theorem plays in the development:

a proposition is a theorem of moderate scope, generally local to a chapter or a section;
a lemma is a preparatory theorem used to break a larger result into smaller pieces;
a corollary is a theorem that follows almost immediately from a previous one;
a characterization is a theorem giving a condition equivalent to a definition --- at heart, an alternative redefinition.

Example — Definition / characterization pair

Definition of an increasing function: let $I$ be an interval and $f \colon I \to \mathbb{R}$ a function. We say $f$ is increasing on $I$ if $$ \forall x, y \in I, \quad x < y \;\Longrightarrow\; f(x) \le f(y). $$ Characterization: let $I$ be an interval with non-empty interior, and let $f \colon I \to \mathbb{R}$ be continuous on $I$ and differentiable on the interior of $I$. Then $f$ is increasing on $I$ if and only if $f'(x) \ge 0$ for every $x$ in the interior of $I$.
The definition fixes the meaning of the word increasing using the order on $\mathbb{R}$. The characterization is a theorem that recasts this meaning into a condition on $f'$ --- useful in practice because it reduces checking increasing to a sign computation.

Pitfall --- no homonymy

In a single reasoning, each symbol has exactly one meaning. Re-using the letter $K$ for two different quantities in the same proof creates an ambiguity that breaks the rigour. If a second compound expression needs a short name, choose a different letter. The everyday word verre is tolerated in French to mean both the material and the object --- homonymy is fine in natural language; it is forbidden in mathematics.

Skills to practice

Writing correct definitions and theorem statements

II Introducing an object: Let$\virgule$ Set$\virgule$ Denote

Why introductions matter

The first rule of mathematical writing is that every object you talk about must be introduced first. In ordinary speech, if you say « They worked all evening » without having said who « they » are, no one understands. In mathematics it is the same: writing $\sin(x + \pi/4) = \ldots$ without first declaring what $x$ is leaves the equality void of meaning.
Three verbs do the introducing work, and they are not interchangeable:

Let introduces a generic variable: a placeholder for any element of a given set. The variable lives only for the duration of the proof.
Set introduces a brand-new name on the left, attached to a known expression on the right. The new name is a shortcut: the verb set binds it to its value.
Denote by introduces a notation for an object whose existence is clear from the context or is being defined at that moment. The verb denote marks the act of naming.

Method — Introducing a generic variable

To introduce $x$ as a generic element of a set $E$:

Let $x \in E$.
$\vdots$ $\quad$ (reason about $x$)
The statement is proved for all $x \in E$.

The variable $x$ is born at the « Let » and dies when the proof ends. The introduction can also be done collectively for a quantified statement: For every $x \in E$, followed by the property to be established.

Method — Naming a specific object: Set vs Denote

To attach a short name $K$ to a previously-introduced quantity:

Set $K = \tfrac{e^\alpha + 1}{\alpha^2 + 1}$. $\quad$ (you create the name $K$ and bind it to the value; valid only if $\alpha$ has been introduced beforehand)
Denote by $K$ the real number $\tfrac{e^\alpha + 1}{\alpha^2 + 1}$. $\quad$ (the real number exists; you give it a name)

Two rules are imperative:

the new name (here $K$) must not already be in use in the reasoning;
the right-hand side must use only previously-introduced objects (here $\alpha$).

Example — Three correct openings

The trigonometric identity $\sin(x + \tfrac{\pi}{4}) = \tfrac{\sin x + \cos x}{\sqrt{2}}$ holds for every real $x$. Three valid openings:

Let $x \in \mathbb{R}$. $\quad$ Then $\sin(x + \tfrac{\pi}{4}) = \sin x \cos \tfrac{\pi}{4} + \cos x \sin \tfrac{\pi}{4} = \tfrac{\sin x + \cos x}{\sqrt{2}}.$
For every $x \in \mathbb{R}$, $\sin(x + \tfrac{\pi}{4}) = \sin x \cos \tfrac{\pi}{4} + \cos x \sin \tfrac{\pi}{4} = \tfrac{\sin x + \cos x}{\sqrt{2}}.$
Inside a quantified sum or integral expression, the symbol introduces itself: $\sum_{k=1}^n \sqrt{k}$ requires no « Let » for $k$. The variable $n$, on the other hand, must be introduced beforehand.

What is not acceptable is writing the identity alone, with no introduction of $x$ --- the equality would then be void of meaning (about what $x$?).

Example — Set vs Denote on a concrete quantity

Suppose $\alpha \in \mathbb{R}$ has already been introduced. We want to give the short name $K$ to the real number $\tfrac{e^\alpha + 1}{\alpha^2 + 1}$. Both following formulations are correct and equivalent:

Set $K = \tfrac{e^\alpha + 1}{\alpha^2 + 1}$.
Denote by $K$ the real number $\tfrac{e^\alpha + 1}{\alpha^2 + 1}$.

Note that the new letter $K$ appears on the left of the equality, the known quantity on the right. The opposite formulation Set $\tfrac{e^\alpha + 1}{\alpha^2 + 1} = K$ should be avoided: it obscures which symbol is being introduced.

Pitfall --- existence requires justification

It is not enough to wish that an object exists for it to exist. If you write « Denote by $N$ the largest positive integer », you are presupposing that such an $N$ exists. It does not (the natural numbers are unbounded). Any subsequent reasoning starting from this $N$ is empty. Before introducing $N$ with Denote by, the existence of $N$ must be either obvious or proved.

Skills to practice

Marking a student copy: introductions
Writing correct introductions

III Proving universal and existential propositions

Two flavours of quantifier

A universal proposition has the form $\forall x \in E, \, P(x)$: « for every $x$ in $E$, the property $P(x)$ holds ». An existential proposition has the form $\exists x \in E, \, P(x)$: « there exists $x$ in $E$ such that $P(x)$ holds ». The two are proved by opposite movements: a universal proof starts with Let $x \in E$ and shows the property for a generic $x$; an existential proof exhibits one specific $x$ and verifies the property on it.

Method — Proving a universal proposition

Let $x \in E$. We show $P(x)$.
$\vdots$ $\quad$ (proof of $P(x)$ for this generic $x$)
Hence $P(x)$ holds for every $x \in E$.

The key is that $x$ is generic: nothing in the proof should rely on a specific value of $x$.

Example — A universal inequality

Show that for every $x \in \mathbb{R}$, $\tfrac{x}{x^2 + 1} \le \tfrac{1}{2}$.

Answer

Let $x \in \mathbb{R}$. The inequality $(x - 1)^2 \ge 0$ holds because the square of a real is non-negative. Expanding, $$ x^2 - 2x + 1 \ge 0, \qquad \text{i.e.} \qquad x^2 + 1 \ge 2x. $$ Since $x^2 + 1 > 0$, dividing by $x^2 + 1$ preserves the inequality: $$ \frac{2x}{x^2 + 1} \le 1, \qquad \text{i.e.} \qquad \frac{x}{x^2 + 1} \le \frac{1}{2}. $$ Hence $\tfrac{x}{x^2 + 1} \le \tfrac{1}{2}$ for every $x \in \mathbb{R}$.

Method — Proving an existential proposition

Exhibit one specific $x$ that satisfies $P$:

Set $x = \ldots$ (the explicit candidate).
Check $P(x)$: $\vdots$ (verification on this specific $x$)
Hence $\exists x \in E$ such that $P(x)$.

The hard part is usually finding the candidate; the verification is then routine. The opening uses Set, not Let, because $x$ is a specific object that we construct.

Example — An existence statement with universally-quantified parameters

Show that for every $x, y \in \mathbb{N}$, there exists $z \in \mathbb{N}$ such that $\sqrt{z} > x + y$.

Answer

Let $x, y \in \mathbb{N}$. Set $z = (x + y + 1)^2$. Then $z \in \mathbb{N}$ as a square of a natural number. Moreover, $$ \sqrt{z} = |x + y + 1| = x + y + 1 > x + y, $$ the absolute value being unnecessary since $x + y + 1 \ge 1 > 0$. Hence $z$ satisfies the desired property.
Hence for every $x, y \in \mathbb{N}$, there exists $z \in \mathbb{N}$ such that $\sqrt{z} > x + y$.

Skills to practice

Writing correct universal and existential proofs

IV Proving uniqueness

Two flavours of uniqueness

Two phrasings should not be confused:

« At most one $x \in E$ satisfies $P$ » --- uniqueness alone. It does not claim the existence of $x$; it only says that if such an $x$ exists, there is at most one.
$\exists ! \, x \in E, \, P(x)$ (read « there exists a unique $x$ ») --- existence and uniqueness. The symbol $\exists !$ packs both claims.

In a proof of $\exists !$, the two pieces are demonstrated separately: existence (exhibit one $x$) and uniqueness (show any two candidates coincide).

Method — Proving uniqueness

To show that at most one $x \in E$ satisfies $P$:

Let $x, x' \in E$.
Assume $P(x)$ and $P(x')$.
Show $x = x'$.
$\vdots \quad$ (algebraic / set-theoretic argument)

There is no need to argue by contradiction « suppose $x \ne x'$ » --- directly showing that two candidates coincide is shorter and cleaner.

Example — Existence and uniqueness of a positive square root

Show that there exists a unique $x \in \mathbb{R}_+$ such that $x^2 = 1$.

Answer

Existence. Set $x = 1$. Then $x \in \mathbb{R}_+$ and $x^2 = 1$.
Uniqueness. Let $x, x' \in \mathbb{R}_+$. Assume $x^2 = 1$ and $x'^2 = 1$. Then $0 = x^2 - x'^2 = (x - x')(x + x')$. Since $x \ge 0$ and $x' \ge 0$, the factor $x + x' \ge 0$. If $x + x' = 0$, then $x = x' = 0$ (a sum of two non-negative reals is zero only if both are zero), which contradicts $x^2 = 1$; so $x + x' > 0$, and therefore $x - x' = 0$, i.e.\ $x = x'$.
Hence there is a unique $x \in \mathbb{R}_+$ such that $x^2 = 1$ (namely $x = 1$).

Pitfall --- at most one is not exactly one

The phrase at most one is a uniqueness statement without existence. By contrast, exactly one (or the symbol $\exists !$) bundles existence and uniqueness. The error of writing « at most one » to mean $\exists !$ is common: it leaves the existence half of the result implicit and unproven. In a proof of $\exists !$, never begin with uniqueness alone and then conclude existence: showing that two possible objects would be equal does not show that one exists.

Skills to practice

Writing correct uniqueness proofs

V Disjunction$\virgule$ implication$\virgule$ equivalence

Three connectives and their proof templates

Three logical connectives appear constantly: « $p$ ou $q$ », « $p \Rightarrow q$ », « $p \iff q$ ». Each has a specific proof template. We also need to know how to disprove an implication or an equivalence, which means producing a counterexample.

Method — Proving a disjunction

The propositions « $p$ or $q$ » and « (not $p$) $\Rightarrow q$ » are equivalent. Hence:

Assume $p$ is false.
$\vdots$ $\quad$ (proof of $q$)
Therefore $q$ is true, and hence « $p$ or $q$ » is true.

Example — A maximum is bounded below

Show that for every $x \in \mathbb{R}$, $\max\{x^2, (x-2)^2\} \ge 1$.

Answer

Let $x \in \mathbb{R}$. The statement to prove is « $x^2 \ge 1$ or $(x-2)^2 \ge 1$ ». Assume $x^2 < 1$. Then $-1 < x < 1$, hence $-3 < x - 2 < -1$. The square function is decreasing on $\mathbb{R}_-$, and $-3 < x - 2 < -1 \le 0$, so $(x - 2)^2 \ge (-1)^2 = 1$.
Hence either $x^2 \ge 1$ or $(x - 2)^2 \ge 1$, so in every case $\max\{x^2, (x-2)^2\} \ge 1$.

Method — Proving an implication

Assume $p$ is true.
$\vdots$ $\quad$ (proof of $q$ from $p$)
Therefore $q$, and the implication « $p \Rightarrow q$ » is proved.

Example — An implication restricting the solution set

Show that for every $x \in [0, 1]$, $x - x^2 \in \mathbb{N} \Rightarrow x \in \{0, 1\}$.

Answer

Let $x \in [0, 1]$. Assume $x - x^2 \in \mathbb{N}$. We have $0 \le x \le 1$, hence $0 \le x^2 \le x$, hence $0 \le x - x^2$. For the upper bound, use the algebraic identity $$ x - x^2 = \frac{1}{4} - \left( x - \frac{1}{2} \right)^2 \le \frac{1}{4}, $$ the square being non-negative. Hence $0 \le x - x^2 \le 1/4$.
The only natural number in $[0, 1/4]$ is $0$, so $x - x^2 = 0$, i.e.\ $x(1 - x) = 0$, i.e.\ $x = 0$ or $x = 1$.
Therefore $x \in \{0, 1\}$.

Pitfall --- the implication arrow is not the word therefore

The symbol $\Rightarrow$ is a logical connective that builds the proposition « $p \Rightarrow q$ », not a punctuation mark meaning « therefore » or « hence ». A typical wrong formulation reads: $$ 0 \le x \le 1 \;\Rightarrow\; 0 \le x^2 \le 1 \;\Rightarrow\; 0 \le 1 - x^2 \le 1 \;\Rightarrow\; \sqrt{1 - x^2} \in [0, 1]. $$ This is not a proof --- it is a chain of implications without an introduced $x$ and without articulation words. The correct formulation is: \begin{quote} Let $x \in [0, 1]$. By growth of the square function on $\mathbb{R}_+$, $0 \le x^2 \le 1$. Therefore $0 \le 1 - x^2 \le 1$. The square root function being increasing, hence $0 \le \sqrt{1 - x^2} \le 1$, that is, $\sqrt{1 - x^2} \in [0, 1]$. \end{quote} In practice the implication arrow is rare in the body of a proof. Use therefore, thus, consequently, hence, so, etc., to articulate the reasoning.

Method — Proving an implication by contrapositive

To prove « $p \Rightarrow q$ », one may instead prove its contrapositive « (not $q$) $\Rightarrow$ (not $p$) ». The two implications are logically equivalent.

Assume not $q$.
$\vdots$ $\quad$ (proof of not $p$)
Therefore not $p$. By contrapositive, $p \Rightarrow q$.

This template is useful when « not $q$ » is easier to manipulate than $p$ --- typically when $p$ is an existence statement that is hard to use directly.

Method — Negating quantified statements

The two negation rules for quantifiers are: $$ \text{not} \bigl( \forall x \in E, \, P(x) \bigr) \iff \exists x \in E, \, \text{not } P(x), $$ $$ \text{not} \bigl( \exists x \in E, \, P(x) \bigr) \iff \forall x \in E, \, \text{not } P(x). $$ Quantifiers switch when negated: $\forall$ becomes $\exists$ and $\exists$ becomes $\forall$. Combined with the rule « not $(p \Rightarrow q) \iff p$ and (not $q$) », these are the foundation of counterexamples and of proof by contradiction.

Method — Disproving an implication

The proposition « not $(p \Rightarrow q)$ » is equivalent to « $p$ and (not $q$) ». To disprove « $\forall x \in E, \, p(x) \Rightarrow q(x) $ », exhibit one $x \in E$ for which $p(x)$ is true and $q(x)$ is false.

Example — A failed implication for sine

Show that the proposition $\forall x, y \in \mathbb{R}, \, x < y \Rightarrow \sin x \le \sin y$ is false.

Answer

The negation reads $\exists x, y \in \mathbb{R}, \, x < y$ and $\sin x > \sin y$. Set $x = \tfrac{\pi}{2}$ and $y = \pi$. Then $x, y \in \mathbb{R}$ and $x < y$ (since $\tfrac{\pi}{2} < \pi$). Moreover $\sin x = \sin \tfrac{\pi}{2} = 1$ and $\sin y = \sin \pi = 0$, hence $\sin x > \sin y$.
Hence the proposition is false.

Method — Proving an equivalence

Two approaches:

By double implication. Prove $p \Rightarrow q$ and $q \Rightarrow p$ separately.
By chain of equivalences. Find intermediate propositions $r, s, \ldots$ such that $p \iff r \iff s \iff \cdots \iff q$, each $\iff$ holding by an explicit reason.

Example — Equivalence by chain of equivalences

Show that for every $x, y \in \mathbb{R}$, $x^2 + y^2 = 0 \iff x = y = 0$.

Answer

Let $x, y \in \mathbb{R}$. Since $x^2 \ge 0$ and $y^2 \ge 0$, the sum $x^2 + y^2$ is a sum of non-negative reals, hence vanishes if and only if each summand vanishes: $$ x^2 + y^2 = 0 \iff (x^2 = 0 \text{ and } y^2 = 0) \iff (x = 0 \text{ and } y = 0). $$ Each equivalence is justified: the first by « a sum of non-negative reals is zero iff each term is zero », the second by « $t^2 = 0 \iff t = 0$ ».
Hence for every $x, y \in \mathbb{R}$, $x^2 + y^2 = 0 \iff x = y = 0$.

Pitfall --- the double arrow is not the abbreviation i.e.

The double arrow $\iff$ commits you to a proof in both directions. It is the symbol of « if and only if ». In a derivation where you simply wish to say « that is » or « i.e. » (rewriting the same statement in a clearer form), use the words; do not write $\iff$. Use $\iff$ only when the transformation is genuinely reversible. Each equivalence must be either obvious (e.g.\ $x + 1 = 3 \iff x = 2$) or explicitly justified.

Skills to practice

Marking a student copy: implication arrow and equivalence
Writing correct logical proofs

VI Set inclusion and equality

From elements to sets

Set assertions reduce to logical assertions on elements: $E \subset F$ means $\forall x, \, x \in E \Rightarrow x \in F$. Inclusion is proved by introducing a generic element of the smaller set; equality is proved by double inclusion (two passages) or by a chain of equivalences (one passage).

Method — Proving an inclusion

Let $x \in E$.
$\vdots$ $\quad$ (deduce $x \in F$ from $x \in E$)
Therefore $x \in F$, and $E \subset F$.

Example — A small inclusion

Show that $\{ x \in \mathbb{R} \mid \exists y \in \mathbb{R}_+, \, x \ge y \} \subset \mathbb{R}_+$.

Answer

Let $x$ be an element of the left-hand side. By definition, $x \in \mathbb{R}$ and there exists $y \in \mathbb{R}_+$ with $x \ge y$. Hence $x \ge y \ge 0$, so $x \in \mathbb{R}_+$.
Therefore $\{ x \in \mathbb{R} \mid \exists y \in \mathbb{R}_+, \, x \ge y \} \subset \mathbb{R}_+$. The reverse inclusion is immediate by choosing $y = 0$, so the two sets are in fact equal.

Method — Proving a set equality

Two approaches:

By double inclusion. Prove $E \subset F$ (with the previous method) and $F \subset E$ separately.
By chain of equivalences. For every $x$, show $x \in E \iff \cdots \iff x \in F$, each $\iff$ holding by an explicit reason.

The chain method is concise when each step is a clear rewrite; the double-inclusion method is preferable when the two implications have different proofs.

Example — De Morgan for an indexed family

Let $E$ be a set and $(A_i)_{i \in I}$ a family of subsets of $E$. Show that $E \setminus \bigcup_{i \in I} A_i = \bigcap_{i \in I} (E \setminus A_i)$.

Answer

Both sides are subsets of $E$. Let $x \in E$. We chain equivalences: $$ \begin{aligned} x \in E \setminus \bigcup_{i \in I} A_i &\iff x \notin \bigcup_{i \in I} A_i && \text{(by definition of $\setminus$, with $x \in E$ given)} \\ &\iff \text{not} \, \bigl( \exists i \in I, \, x \in A_i \bigr) && \text{(by definition of $\bigcup$)} \\ &\iff \forall i \in I, \, x \notin A_i && \text{(negation of an existential)} \\ &\iff \forall i \in I, \, x \in E \setminus A_i && \text{(by definition of $\setminus$, with $x \in E$ given)} \\ &\iff x \in \bigcap_{i \in I} (E \setminus A_i) && \text{(by definition of $\bigcap$).} \end{aligned} $$ Therefore $E \setminus \bigcup_{i \in I} A_i = \bigcap_{i \in I} (E \setminus A_i)$.

Skills to practice

Writing correct set proofs

VII Proof by induction

The idea of induction

Some properties of integers are best proved by induction: instead of checking the property for each $n$ separately (impossible, since $\mathbb{N}$ is infinite), one shows that the property is « passed on » from $n$ to $n + 1$, starting from a base case. Three flavours are useful here: simple, double, and strong induction. Each rests on a theorem about $\mathbb{N}$ that we admit (the underlying property of $\mathbb{N}$ is outside the syllabus at this level).

Theorem — Simple induction

Let $A \subset \mathbb{N}$. If $0 \in A$ and $\forall n \in \mathbb{N}, \, n \in A \Rightarrow n + 1 \in A$, then $A = \mathbb{N}$.

Admitted statement

The proof of simple induction rests on the construction of $\mathbb{N}$ from more elementary axioms, which is outside the syllabus. We admit the theorem.

Method — Writing a simple induction

To prove $\forall n \in \mathbb{N}, \, P_n$:

Base case. Show $P_0$.
Induction step. Let $n \in \mathbb{N}$. Assume $P_n$. Show $P_{n+1}$.
$\vdots$ $\quad$ (proof of $P_{n+1}$ from $P_n$)
Conclusion. By simple induction, $\forall n \in \mathbb{N}, \, P_n$.

The phrase « Let $n \in \mathbb{N}$. Assume $P_n$. » introduces a single, generic $n$ --- not all $n$ at once.

Method — Induction starting at a non-zero rank

To prove $\forall n \ge n_0, \, P_n$, the simple-induction theorem applies after a translation of indices. In practice:

Base case. Show $P_{n_0}$.
Induction step. Let $n \ge n_0$. Assume $P_n$. Show $P_{n+1}$.
$\vdots$ $\quad$ (proof of $P_{n+1}$ from $P_n$)
Conclusion. By induction starting at rank $n_0$, $\forall n \ge n_0, \, P_n$.

The cases $n_0 = 1$ and $n_0 = 2$ occur constantly in practice (formulas valid only from a certain rank).

Example — A bounded recurrent sequence

Let $(a_n)_{n \in \mathbb{N}}$ be defined by $a_0 = 1$ and $a_{n+1} = 1 + \tfrac{a_n}{n + 1}$ for $n \in \mathbb{N}$. Show that $a_n \le 2$ for every $n \in \mathbb{N}$.

Answer

Let $P_n$ be the property « $a_n \le 2$ ».
Base case. $a_0 = 1 \le 2$, so $P_0$ holds.
Induction step. Let $n \in \mathbb{N}$. Assume $P_n$, i.e.\ $a_n \le 2$. Show $P_{n+1}$. Split on $n = 0$ vs.\ $n \ge 1$:

Case $n = 0$. $a_1 = 1 + \tfrac{a_0}{1} = 1 + 1 = 2 \le 2$, so $P_1$ holds.
Case $n \ge 1$. Since $n + 1 \ge 2$, we have $\tfrac{a_n}{n + 1} \le \tfrac{2}{2} = 1$, hence $a_{n+1} = 1 + \tfrac{a_n}{n + 1} \le 1 + 1 = 2$, i.e.\ $P_{n+1}$ holds.

Conclusion. By simple induction, $\forall n \in \mathbb{N}, \, a_n \le 2$.

Pitfall --- the induction step is for a generic integer

A grave error in induction: opening the induction step with « Assume $P_n$ is true for every $n \in \mathbb{N}$ ». If $P_n$ were already true for all $n$, there would be nothing left to prove. The correct opening is « Let $n \in \mathbb{N}$. Assume $P_n$. » --- one $n$ at a time, and that $n$ is generic, not specific.

Theorem — Double induction

Let $A \subset \mathbb{N}$. If $0 \in A$, $1 \in A$, and $\forall n \in \mathbb{N}, \, (n \in A$ and $n + 1 \in A) \Rightarrow n + 2 \in A$, then $A = \mathbb{N}$.

Admitted statement

The proof reduces to simple induction applied to $B = \{ n \in \mathbb{N} \mid n \in A$ and $n + 1 \in A \}$; like simple induction, we admit it at this level.

Method — Writing a double induction

To prove $\forall n \in \mathbb{N}, \, P_n$, when $P_{n+2}$ depends on both $P_n$ and $P_{n+1}$:

Base case. Show $P_0$ and $P_1$.
Induction step. Let $n \in \mathbb{N}$. Assume $P_n$ and $P_{n+1}$. Show $P_{n+2}$.
$\vdots$
Conclusion. By double induction, $\forall n \in \mathbb{N}, \, P_n$.

Example — An explicit formula by double induction

Let $(u_n)_{n \in \mathbb{N}}$ be defined by $u_0 = 4$, $u_1 = 5$, and $u_{n+2} = 3 u_{n+1} - 2 u_n$ for $n \in \mathbb{N}$. Show that $u_n = 2^n + 3$ for every $n \in \mathbb{N}$.

Answer

Let $P_n$ be the property « $u_n = 2^n + 3$ ».
Base case. $u_0 = 4 = 1 + 3 = 2^0 + 3$, so $P_0$ holds. $u_1 = 5 = 2 + 3 = 2^1 + 3$, so $P_1$ holds.
Induction step. Let $n \in \mathbb{N}$. Assume $P_n$ and $P_{n+1}$, i.e.\ $u_n = 2^n + 3$ and $u_{n+1} = 2^{n+1} + 3$. Show $P_{n+2}$. $$ \begin{aligned} u_{n+2} &= 3 u_{n+1} - 2 u_n \\ &= 3 (2^{n+1} + 3) - 2 (2^n + 3) && \text{(by induction hypothesis)} \\ &= 3 \cdot 2^{n+1} - 2 \cdot 2^n + (9 - 6) \\ &= 3 \cdot 2^{n+1} - 2^{n+1} + 3 \\ &= 2 \cdot 2^{n+1} + 3 \\ &= 2^{n+2} + 3. \end{aligned} $$ Hence $P_{n+2}$ holds.
Conclusion. By double induction, $\forall n \in \mathbb{N}, \, u_n = 2^n + 3$.

Theorem — Strong induction

Let $A \subset \mathbb{N}$. If $0 \in A$ and $\forall n \in \mathbb{N}, \, (\forall k \in \llbracket 0, n \rrbracket, \, k \in A) \Rightarrow n + 1 \in A$, then $A = \mathbb{N}$.

Admitted statement

Strong induction also reduces to simple induction, applied to $B = \{ n \in \mathbb{N} \mid \forall k \in \llbracket 0, n \rrbracket, \, k \in A \}$. We admit it.

Method — Writing a strong induction

To prove $\forall n \in \mathbb{N}, \, P_n$, when $P_{n+1}$ may depend on all of $P_0, \ldots, P_n$:

Base case. Show $P_0$.
Induction step. Let $n \in \mathbb{N}$. Assume $P_k$ for every $k \in \llbracket 0, n \rrbracket$. Show $P_{n+1}$.
$\vdots$
Conclusion. By strong induction, $\forall n \in \mathbb{N}, \, P_n$.

Example — A bound via the sum of previous terms

Let $(v_n)_{n \in \mathbb{N}}$ be a real sequence with $v_0 \ge 0$ and $v_{n+1} \le \sum_{k = 0}^n v_k$ for every $n \in \mathbb{N}$. Show that $v_n \le 2^n v_0$ for every $n \in \mathbb{N}$.

Answer

Let $P_n$ be the property « $v_n \le 2^n v_0$ ».
Base case. $v_0 \le v_0 = 2^0 v_0$, so $P_0$ holds.
Induction step. Let $n \in \mathbb{N}$. Assume $P_k$ for every $k \in \llbracket 0, n \rrbracket$, i.e.\ $v_k \le 2^k v_0$. Show $P_{n+1}$. By hypothesis, $$ \begin{aligned} v_{n+1} &\le \sum_{k = 0}^n v_k && \text{(hypothesis on the sequence)} \\ &\le \sum_{k = 0}^n 2^k v_0 && \text{(strong induction hypothesis; $v_0 \ge 0$ allows summing the inequalities)} \\ &= v_0 \sum_{k = 0}^n 2^k && \text{(linearity)} \\ &= v_0 \cdot \frac{2^{n+1} - 1}{2 - 1} && \text{(geometric sum)} \\ &= (2^{n+1} - 1) v_0 \le 2^{n+1} v_0. \end{aligned} $$ Hence $P_{n+1}$ holds.
Conclusion. By strong induction, $\forall n \in \mathbb{N}, \, v_n \le 2^n v_0$.

Skills to practice

Marking a student copy: heredity
Writing correct induction proofs

VIII Proof by contradiction

The idea

To prove $p$, assume the opposite (not $p$) and derive a contradiction --- a proposition of the form $q$ and (not $q$). If not $p$ leads to such a contradiction, then not $p$ is false, hence $p$ is true.

Method — Writing a proof by contradiction

Argue by contradiction. Assume not $p$.
$\vdots$ $\quad$ (derive a contradiction $q$ and not $q$)
Contradiction. Therefore $p$.

The contradiction must be explicit: a proposition $q$ together with its negation, both established during the reasoning.

Example — A square root that is never an integer

Show that for every $n \in \mathbb{N}$, $\sqrt{n^2 + 2}$ is not an integer.

Answer

Let $n \in \mathbb{N}$. Argue by contradiction. Assume $\sqrt{n^2 + 2}$ to be an integer; denote by $p$ this integer, so that $p \in \mathbb{N}$ and $p^2 = n^2 + 2$. Hence $$ (p - n)(p + n) = p^2 - n^2 = 2. $$ $p$ and $n$ are non-negative, so $p + n \ge 0$. Moreover $p^2 = n^2 + 2 > n^2$ gives $p > n$, hence $p - n \ge 1$ and $p + n \ge p - n \ge 1$. So we have two positive integers whose product is $2$.
The only pair $(a, b)$ of natural numbers with $a \le b$ and $ab = 2$ is $(1, 2)$. Hence $p - n = 1$ and $p + n = 2$, which gives $p = \tfrac{3}{2}$ by adding the two equations and dividing by $2$. But $p \in \mathbb{N}$, so $p \ne \tfrac{3}{2}$.
Contradiction. Therefore $\sqrt{n^2 + 2}$ is not an integer.

Skills to practice

Writing correct contradiction proofs

IX Analysis-synthesis

The detective method

To determine all elements of a set $E$ satisfying a property $P$, we proceed by analysis-synthesis. Analysis. Let $x \in E$ satisfying $P$. From this assumption, derive constraints on $x$ until only finitely many candidates remain. Synthesis. For each candidate, verify that it does belong to $E$ and satisfy $P$.
The analysis half narrows the field of possibilities --- it proves « if a solution exists, it is one of these candidates ». The synthesis half tests each candidate --- it proves « this candidate actually is a solution ». Together they determine the complete set of solutions, which may be empty, a singleton, or have several elements. Uniqueness is established only in the case where that set turns out to be a singleton.

Method — Writing an analysis-synthesis proof

Analysis. Let $x \in E$ satisfying $P$.
$\vdots$ $\quad$ (deduce restrictions on $x$ until candidates are explicit)
Synthesis. For each candidate, verify that it belongs to $E$ and satisfies $P$.
$\vdots$
Conclusion. The set of solutions is $\{ \ldots \}$.

Example — Solving a biquadratic equation

Find all real $x$ such that $x^4 - 4 x^2 + 3 = 0$.

Answer

Analysis. Let $x \in \mathbb{R}$ such that $x^4 - 4 x^2 + 3 = 0$. Set $X = x^2 \ge 0$. Then $$ X^2 - 4 X + 3 = 0 \iff (X - 1)(X - 3) = 0 \iff X = 1 \text{ or } X = 3. $$ Hence $x^2 = 1$ or $x^2 = 3$, so $x \in \{ -\sqrt{3}, -1, 1, \sqrt{3} \}$.
Synthesis. Verify each candidate: $$ \begin{aligned} (\pm 1)^4 - 4 (\pm 1)^2 + 3 &= 1 - 4 + 3 = 0, \\ (\pm \sqrt{3})^4 - 4 (\pm \sqrt{3})^2 + 3 &= 9 - 12 + 3 = 0. \end{aligned} $$ All four candidates satisfy the equation.
Conclusion. The solution set is $\{ -\sqrt{3}, -1, 1, \sqrt{3} \}$.

Example — A functional equation

Find all functions $f \colon \mathbb{R} \to \mathbb{R}$ such that for every $x, y \in \mathbb{R}$, $f(y - f(x)) = 2 - x - y$.

Answer

Analysis. Let $f \colon \mathbb{R} \to \mathbb{R}$ satisfying the equation. In particular, for every $x \in \mathbb{R}$, choosing $y = f(x)$ yields $f(0) = 2 - x - f(x)$, hence $$ f(x) = (2 - f(0)) - x. $$ This computation shows that $f$ is necessarily of the form $x \longmapsto \lambda - x$ for some real $\lambda = 2 - f(0)$.
Synthesis. Let $\lambda \in \mathbb{R}$ and write $f$ for the function $x \longmapsto \lambda - x$. For every $x, y \in \mathbb{R}$, $$ \begin{aligned} f(y - f(x)) &= f(y - (\lambda - x)) \\ &= f(y - \lambda + x) \\ &= \lambda - (y - \lambda + x) \\ &= 2 \lambda - x - y. \end{aligned} $$ We want $2 \lambda - x - y = 2 - x - y$, i.e.\ $\lambda = 1$. Hence the only admissible value of $\lambda$ is $\lambda = 1$.
Conclusion. The unique solution is $f \colon x \longmapsto 1 - x$.

Why analysis-synthesis determines the complete solution set

The analysis half restricts the field of possibilities: it shows that any solution must lie among finitely many candidates (a necessary condition). The synthesis half tests each candidate and keeps those that are solutions (a sufficient condition). Together they yield the exact set of solutions --- exactly those candidates that survive the synthesis. This set may be empty, a singleton, or have several elements: the functional equation above has a single solution, while the biquadratic equation has four. Analysis-synthesis does not prove $\exists !$ automatically; uniqueness is obtained only when the surviving set happens to be a singleton.

Skills to practice

Writing correct analysis-synthesis proofs

X Writing with functions

A function is an object$\virgule$ not an expression

The expression $e^x \sin x$ is a real number depending on $x$, not a function. The function is the rule that sends $x$ to $e^x \sin x$, written $x \longmapsto e^x \sin x$. The distinction matters: « the function $e^x \sin x$ is differentiable » is incorrect; the correct phrasing is « the function $x \longmapsto e^x \sin x$ is differentiable on $\mathbb{R}$ ».

Method — Defining a function

To define a function $f$ from a set $E$ to a set $F$ by a rule, four equivalent formulations are possible:

Denote by $f$ the function from $\mathbb{R}_+$ to $\mathbb{R}$ defined by $x \longmapsto \sqrt{x} + 1$.
Denote by $f$ the function $\begin{cases} \mathbb{R}_+ \longrightarrow \mathbb{R} \\ x \longmapsto \sqrt{x} + 1 \end{cases}$.
Denote by $f \colon \mathbb{R}_+ \to \mathbb{R}$ the function defined for every $x \in \mathbb{R}_+$ by $f(x) = \sqrt{x} + 1$.
Set, for every $x \in \mathbb{R}_+$, $f(x) = \sqrt{x} + 1$, with $f \colon \mathbb{R}_+ \to \mathbb{R}$.

The arrow $\longrightarrow$ goes from set to set (here $\mathbb{R}_+ \longrightarrow \mathbb{R}$); the arrow $\longmapsto$ goes from element to value (here $x \longmapsto \sqrt{x} + 1$). The two arrows are not interchangeable. The codomain $\mathbb{R}$ should be stated even when « obvious », to remove ambiguity.

Method — Speaking about a function

A function is usually said to be differentiable, continuous, increasing, or bounded on a set. One may also say that $f$ is differentiable at every point of a set. What should be avoided is attaching « for every $x$ » directly to the function object $x \longmapsto x^2$, because the function does not depend on $x$ --- the letter is a bound variable in the rule. Hence:

Preferred. The function $x \longmapsto x^2$ is differentiable on $\mathbb{R}$.
Also correct. The function $f$ is differentiable at every point of $\mathbb{R}$.
To avoid. The function $x \longmapsto x^2$ is differentiable for every $x \in \mathbb{R}$.

The « for every $x \in \mathbb{R}$ » phrasing is appropriate when one talks about $f'(x)$ (which does depend on $x$): « For every $x \in \mathbb{R}$, $f'(x) = 2 x$ ».

Example — Computing a derivative cleanly

Differentiate the function $f \colon x \longmapsto e^{\sin(2 x)}$ on $\mathbb{R}$, with clean writing.

Answer

The function $f$ is differentiable on $\mathbb{R}$ as a composite of functions differentiable on $\mathbb{R}$. For every $x \in \mathbb{R}$, by the chain rule, $$ f'(x) = \frac{\mathrm{d}}{\mathrm{d} x} \bigl( e^{\sin(2 x)} \bigr) = \frac{\mathrm{d}}{\mathrm{d} x} \bigl( \sin(2 x) \bigr) \cdot e^{\sin(2 x)} = 2 \cos(2 x) \cdot e^{\sin(2 x)}. $$ Note: the notation $(f(x))'$ is forbidden; the notation $\tfrac{\mathrm{d}}{\mathrm{d} x}$ makes the variable of differentiation explicit.

Pitfall --- distinguishing the two function arrows

$\longrightarrow$ goes from set to set; $\longmapsto$ goes from element to value. Writing « $x \longrightarrow e^{x^2}$ » to describe a function is incorrect --- the rule from $x$ to its image uses the arrow with a bar, $\longmapsto$. The single arrow $\longrightarrow$ is reserved for the source/target sets of a function or for the notion of limit (« $f(x) \longrightarrow \ell$ as $x \to a$ »).

Pitfall --- the primed-parenthesis notation is forbidden

The notation $(f(x))'$ should be avoided in rigorous writing because it does not specify clearly whether one differentiates the function $f$ or the expression $f(x)$ with respect to $x$. To write the derivative of the function $f$ at the point $x$, use $f'(x)$. To indicate explicitly that one differentiates with respect to $x$, use the Leibniz notation $\tfrac{\mathrm{d}}{\mathrm{d} x} \bigl( f(x) \bigr)$ --- especially valuable when several variables are in play.

Skills to practice

Marking a student copy: function notation
Writing correct function formulations