# Proofs â€‹

## Proof Templates: â€‹

the fancy english/structure you have to write to get the full points

In all cases it is good to write the info before starting the proof.

*italic* text is supposed to be filled in or replaced in the actual proof.

### Counterexample: â€‹

The statement is false for n = *value goes here*

*(show why it is false for n = value)*

### Proof by cases: â€‹

Make sure that the cases put together form the entire set you are trying to prove the proposition for.

**info:** `S(n):`

*(...)*

**Proof:** By cases we distinguish *two* cases

Case one: *(...)*

Case two: *(...)*

In both cases we proved S(x), since for each *case one* or *case two* we proved that S(x) holds for all

### Direct proof: â€‹

**info:** `S(n):`

*(...)*

**Proof:** take an arbitrary integer x such that x *fufills conditions*

### Proof by contradiction: â€‹

**info:** P -> Q

**Proof:** Assume, for the sake of contradiction *P* is true but *Q* is false.

*(...)*

Since we have a contradiction, it must be that *Q* is true.

### Proof by Induction: â€‹

**info:** `S(n):`

*(...)*

**PROOF:** By mathematical induction.

Basis Step: S(1) asserts that *(...)*

which is true because *(...)*

Inductive Step:

Assume for an arbitrary *(...)* `Induction Hypothesis (substitute k for n)`

We will now show that S(k+1) is also true, i.e.: *(...)* `state what must be proved (substitute k+1 for n)`

Proof of inductive step: *(...)*

Conclusion: We thus have that S(1) is true and

## Sources â€‹

- Harry Aarts, Ed Brinksma, Jan Willem Polderman, Gerhard Post, Marc Uetz, Marjan van der Velde (2018) Introduction to Mathematics
- Micro-lectures wk2
- villanova-induction-template-pdf