Calculate $x^{m}+x^{m+1}+x^{m+2}+\ldots+x^{n-2}+x^{n-1}+x^{n}$, with $x \neq 1$ and $m<n$.
On a $x^{m}+\ldots+x^{n-1}+x^{n}=x^{m}\left(1+\ldots+x^{n-m-1}+x^{n-m}\right)=x^{m}\left(1^{n-m}+1^{n-m-1} x+\ldots+1 \times\right.$ $x^{n-m-1}+x^{n-m}=x^{m}\left(\frac{x^{n-m+1}-1}{x-1}\right)=\frac{x^{n+1}-x^{m}}{x-1}$

## Implication, equivalence, negation

This part of the course gathers important definitions of logic that are mainly there to lay the groundwork for the next part. As long as you master the following part, there is no point in knowing this one in all its details.

Definition 7 (Implication).

Let A and B be two sentences, which can be true or false (also called propositions). We say that A implies B (denoted $A \Longrightarrow B$) if whenever A is true, B is also true.

Example 8. If A is the sentence "I killed Bob" and B is the sentence "Bob is dead", we have A implies B: if I killed Bob, Bob is necessarily dead.

A slightly more mathematical example might be: if $x \geqslant 1$, then $x \geqslant 0$.

In general, we spot an implication (for example in a statement) by the presence of an "if", often followed by a "then".

## Example 9.

Let $a, b>0$. Show that if $a+b=2$, then $a b \leqslant 1$.

Definition 10 (Equivalence).

We can see from all these examples that B can be true without A being true: just because Bob is dead doesn't mean I killed him!

Sometimes we want A to be true exactly when B is true: we want $A \Longrightarrow B$ and $B \Longrightarrow A$. We call this an equivalence, denoted $A \Longleftrightarrow B$, we then say that A is equivalent to B, or that A and B are equivalent, or A if and only if B.

## Example 11.

If A is the sentence $x \geqslant 0$ and B is the sentence $x^{3} \geqslant 0$, we have $A \Longleftrightarrow B$.

(Yes, the first example is a mathematical example, try to find two equivalent sentences from everyday life that are not simply a basic reformulation of each other)

Definition 12 (Negation).

If we are given a proposition A (so a sentence that can be true or false), the negation of A is the opposite of A, denoted $\neg A$.

Put in more complicated terms, $\neg A$ is such that "A is true" $\Longleftrightarrow$ " $\neg A$ is false".

## Example 13.

If A is the proposition "Bob is dead", its negation is "Bob is alive".

If A is "For all $x>0, x^{2}+2 x-3>0$", its negation is "There exists $x>0$ such that $x^{2}+2 x-3 \leqslant 0$".

These definitions are not very interesting in themselves, but they allow solving many problems if they are used in complex and constructed reasoning.

Definition 14 (Proof by Contradiction).

Proof by contradiction is a method that allows proving that a statement is true by showing that its opposite is false. It relies on the logical rule that:

If "not P" is false, then P is true. In other words, the idea is to assume $\neg A$ and arrive at a contradiction, something that is always false (like $0>1$). This means that $\neg A$ is necessarily false, so A is true.

## Example 15.

Let's show that $\sqrt{2}$ cannot be written as a ratio of two integers, we say that $\sqrt{2}$ is irrational.

Suppose, for the sake of contradiction, that $\sqrt{2}$ is rational, so there exist integers $a, b$ such that $\sqrt{2}=\frac{a}{b}$. Then we have $\frac{a^{2}}{b^{2}}=2$, or $a^{2}=2 b^{2}$. At this point, we notice that $a^{2}$ is even, so $a$ is even, and it can be written as $a=2 a^{\prime}$.

We substitute our new expression for $a$ into the initial equation, and we find $b^{2}=2 a^{\prime 2}$. Thus, $b^{2}$ is even, and we have $b=2 b^{\prime}$. Substituting, we get $a^{\prime 2}=2 b^{\prime 2}$. This solution looks a lot like the initial solution, since we also have $\sqrt{2}=\frac{a^{\prime}}{b^{\prime}}$. Moreover, the solution is strictly smaller than before. If we continue this way, we will find a solution that gets smaller and smaller while remaining in the integers, which is not possible since $a \geqslant 1$ and $b \geqslant 1$, at some point this will no longer be the case.

We call such a reasoning an infinite descent.