What 0 0 1 then prove

content
“What is complete induction
" An example
»Tips for conducting induction proofs

What is complete induction?

The method of complete induction is mostly used when an assertion is to be shown for all natural numbers. It works with a kind of domino effect: we have to push it once at the beginning (induction start) and we have to ensure that each domino overturns its successor (induction step).

To put it a bit more mathematically: For each \ (n \ in \ mathbb {N} \) let \ (A (n) \) be a statement (depending on \ (n \), otherwise the induction does not work). The induction proof consists of

  • Induction start: Show that \ (A (1) \) is true.
  • Induction assumption (or induction hypothesis): \ (A (m) \) holds.
  • Induction claim: \ (A (m + 1) \) holds.
  • Induction conclusion (or proof or step): Show the induction claim with the help of the induction hypothesis.

Then \ (A (n) \) is true for every \ (n \ in \ mathbb {N} \). Induction assumption, assertion and conclusion are often summarized under the term induction step.

An example

A nice example, in which one can use complete induction, is the Gaussian sum formula: For all \ (n \ geq 1 \) \ (\ sum_ {k = 1} ^ nk = \ frac {n (n + 1)} applies {2} \).

Induction start: We show that the formula for \ (n = 1 \) is correct: \ begin {align *} \ sum_ {k = 1} ^ 1 k = 1 = \ frac {2} {2} = \ frac { 1 (1 + 1)} {2} \ end {align *}

Induction step: Let \ (m \ in \ mathbb {N} \) and the sum formula for \ (n = m \) already proven. We show that the formula also holds for \ (n = m + 1 \): \ begin {align *} \ sum_ {k = 1} ^ {m + 1} k & = (\ sum_ {k = 1} ^ mk) + (m + 1) \ & = \ frac {m (m + 1)} {2} + \ frac {2 (m + 1)} {2} \ & = \ frac {(m + 2 ) (m + 1)} {2} \ & = \ frac {(m + 1) ((m + 1) +1)} {2} \ end {align *}

 

 

Tips for conducting induction proofs

It is often relatively easy to show the induction start and a little harder to show the induction step. So how does one come up with the proof of the induction step?

First, it helps to find a way to use the induction hypothesis. In our example we have extracted the last summand from the summation sign and could immediately use the assumption that the formula for \ (n = m \) applies.

After that, one must not lose sight of the goal. You can start the proof from both sides on a scrap of paper and hope that the beginnings will meet at some point. Only then do you write down the bill properly from left to right.

content
“The implication
“The counterposition
" An example

The implication

Using contraposition is one way to prove implication.

Let \ (A \) and \ (B \) be statements. An implication is a statement of the form "If \ (A \), then \ (B \)" or in characters \ (A \ Rightarrow B \).

Danger! Nothing is said here about whether \ (A \) is true or whether \ (B \) is true. It's only about the relationship between \ (A \) and \ (B \). So: If \ (A \) should be true, then it would follow that \ (B \) is also true.

The counterposition

The contraposition to the implication "If \ (A \), then \ (B \)" is the statement "If not \ (B \), then \ (A \)". Both are logically equivalent, which can be seen in this truth value table:

A.B.\ (\ lnot A \)\ (\ lnot B \)\ (A \ Rightarrow B \)\ (\ lnot B \ Rightarrow \ lnot A \)
W.W.F.F.W.W.
W.F.F.W.F.F.
F.W.W.F.W.W.
F.F.W.W.W.W.

If the assertion of a sentence is an implication, then one can show the contraposition instead, which is sometimes easier.

An example

Let \ (a \) be a natural number. We want to show the following implication: If \ (a ^ 2 \) is odd, then \ (a \) is also odd.

Formulate the contraposition of the assertion

Our implication "If \ (A \), then \ (B \)" consists of the parts \ begin {align *} A \ &: \ a ^ 2 \ text {is odd and} \ B \ &: \ a \ text {is odd.} \ end {align *}

 

The contraposition "If not \ (B \), then not \ (A \)" is thus "If \ (a \) is not odd, \ (a ^ 2 \) is not odd either". We can rephrase that to "If \ (a \) is even, \ (a ^ 2 \) is even".

Prove the counterposition

Let \ (a \) be an even number. Then there is a natural number \ (k \) such that \ (a = 2 \ cdot k \). Now we calculate \ (a ^ 2 \): \ begin {align *} a ^ 2 = (2k) ^ 2 = 4 k ^ 2 = 2 (2k ^ 2) \ end {align *} Therefore, \ (a ^ 2 \) an even number.

content
“Direct evidence
»Indirect or contradiction proof
“Example of a contradiction proof

Direct evidence

The straightforwardness of direct proof makes it an intuitive approach to proofing. At the beginning there are axioms, mathematical propositions that have already been proven, and the prerequisites of the proposition to be proven. Then logical inferences are drawn until the proposition of the sentence is shown. The inferences are often of the form: We know that the implication "If \ (A \) then \ (B \)" is true. The statement \ (A \) is one of our premises. So \ (B \) is also true, and we can use \ (B \) to prove further statements.

A small example: We show that \ (25 \) is not a prime number. (If you don't know what a prime number is, you can read it here: [Link]) We know that \ (5 \ cdot 5 = 25 \). Therefore \ (5 \) is a divisor of \ (25 \), and it is \ (1 \ neq 5 \ neq 25 \). So \ (25 \) cannot be a prime number.

Indirect or contradiction proof

The contradiction proof (or indirect proof) works fundamentally different. Here it is initially assumed that the statement to be proven is false. A contradiction is then brought about through logical inferences, e.g. one shows that one of the premises (which are assumed to be true) is false. Since that cannot be the case, the assumption must be false and the statement to be proven must be true.

Here, too, a small example: We show again that \ (25 \) is not a prime number. Assume that \ (25 \) is a prime number after all. Then \ (1 \) and \ (25 \) must be the only divisors of \ (25 \). But it is \ (5 \ cdot 5 = 25 \) is, so \ (5 \) is a divisor of \ (25 \). Contradiction!

Example of a contradiction proof

As a longer example we would like to show Euclid's theorem. This says: There are infinitely many prime numbers.

We assume: There are only finitely many prime numbers. Now let's try to create a contradiction.

If there are only finitely many prime numbers \ (2, 3, 5, 7, \ dots \), then we can find them in the set \ (P: = \ {p_1, \ dots, p_k \} \) with a \ ( k \ in \ mathbb {N} \). \ (P \) is the set of all prime numbers that exist!

Now we consider the product of all prime numbers and add 1, i.e. \ (n: = p_1 \ cdot \ dots \ cdot p_k +1 \). According to the fundamental theorem of arithmetic, this number has a prime factorization.

For every prime number \ (p_i \ in P \), however, \ (p_i \) is not a divisor of \ (n \), because when \ (n \) is divided by \ (p_i \), the remainder remains 1 . If \ (q \) is one of the factors from the prime factorization of \ (n \), then \ (q \ notin P \), but \ (q \) is a prime number. This contradicts the fact that \ (P \) is the set of all prime numbers.

content
“The two kinds of proofs of existence
“Examples of proofs of existence

The two kinds of proofs of existence

Some mathematical theorems say that an object with a certain property exists. There are two fundamentally different methods of proving these theorems:

1. Constructive proof: You specify an object and show that it has the required properties; or one gives a method to find such an object. This adds the additional information to the record as to how an object with the required properties can look.

2. Non-constructive proof: One shows with the help of logical inferences (and possibly other propositions) that such an object must exist, but does not indicate how it can be found. This proof can also be used as evidence of contradiction. (Assuming there was no object with these properties, then ...)

Examples of proofs of existence

Let \ (f: \ mathbb {R} \ rightarrow \ mathbb {R} \) be defined by \ (f (x) = -x ^ 2 + 1 \). We show: \ (f \) has (at least) one zero.

1st variant: constructive proof

To show that \ (f \) has a zero, we can simply specify a zero. Such a zero is the number 1. We can prove this by inserting it: \ (f (1) = -1 ^ 2 + 1 = -1 + 1 = 0 \). Therefore \ (f \) has at least one zero.

2nd variant: non-constructive proof

For this proof we need the intermediate value theorem. This is as follows:

If a function \ (f \) is defined and continuous on the interval \ ([a, b] \), then \ (f \) takes all values ​​between \ (f (a) \) and \ (f (b) \ ) in the interval \ ([a, b] \) at least once.

We are looking for a way to apply the intermediate value theorem. To do this, try different values ​​in \ (f \): \ begin {align *} f (0) & = 0 ^ 2 + 1 = 1> 0 \ f (2) & = -2 ^ 2 + 1 = - 4 +1 = -3 <0 \ end {align *}

In order to be able to apply the intermediate value theorem, we must first check the requirements. We put \ (a = 0 \) and \ (b = 2 \). The function \ (f \) is defined over the whole of \ (\ mathbb {R} \), thus also in the interval \ ([0,2] \). As a polynomial function, \ (f \) is continuous in the entire domain, i.e. also in the interval \ ([0,2] \). Therefore we can apply the intermediate value theorem and get: \ (f \) takes every value between \ (f (0) = 1 \) and \ (f (2) = - 3 \) in the interval \ ([0,2] \) ) at least once. In particular, \ (f \) has a zero in this interval.

content
“What do we need evidence for?
“How does a proof work?

What do we need evidence for?

A lot of math is done in school at school. The science of mathematics as taught at university is much more than that. This picture tries to explain that:

 


Image sketch of the mathematical building.svg from Wikimedia Commons, which was created by Golmman and is licensed under CC BY 4.0.

The foundation for mathematics are the axioms. These are basic mathematical statements that are taken to be true. An example of this is "Every natural number \ (n \) has exactly one successor \ (n + 1 \)." Based on this, mathematical propositions (also called theorems) are formulated. These have to be proven in order to be accepted as true by mathematicians. So the proofs are the mortar on the house of mathematics; they hold everything together.

How does a proof work?


Image Structure of a proof.svg from Wikimedia Commons, which was created by Stephan Kulla and is licensed under CC BY 3.0.

The boxes represent statements, the arrows represent mathematical conclusions. Everything starts with the premises, the statements from which we start. These can be axioms or other mathematical theorems that have already been proven. Starting from these, only logical conclusions are allowed in order to arrive at the statement of the sentence with a few intermediate steps. For example, a corollary might look like this: We know that the implication "If \ (A \) then \ (B \)" is true. The statement \ (A \) is one of our premises. So \ (B \) is also true, and we can use \ (B \) to prove further statements.