Mathematics for Applied Sciences (Osnabrück 2023-2024)/Part I/Exercise sheet 2



Exercises

Negate the statement "in the break, all children eat a slice of bread with butter or an apple“, using an existence statement.


Lucy Sonnenschein
Lucy Sonnenschein

We consider the sentence "Lucy Sonnenschein dances on all weddings“. Negate this sentence, using an existence statement.


Formulate the following statements using suitable predicates. Formulate also the negation of the statements (colloquial as well as formally).

  1. All birds are already here.
  2. All streets lead to Rome.
  3. Idleness is the beginning of all vice.
  4. All humans become brothers, Where thy gentle wing abides.


Formulate the following unary predicates within the natural numbers , only using equality, addition, multiplication and logical connectives and quantifiers.

  1. is a multiple of .
  2. is larger than .
  3. is smaller than .
  4. is a square number.
  5. is not a square number.
  6. is a prime number.
  7. is not a prime number.
  8. is the product of exactly two distinct prime numbers.


We consider the sentences "For every pot there is a lid“ and "There is a lid for every pot“, which, in everyday life, are considered to mean the same. But when we understand the statements in the strict sense of predicate logic, reading them from the beginning to the end, two distinct meanings occur.

  1. Formulate the statements with the help of additional words so that the two distinct meanings become apparent.
  2. Let denote the set of pots and let be the set of lids. Let denote the binary predicate such that (for and ) means that is suitable for . Formulate both sentences with appropriate mathematical symbols.
  3. Can we infer logically from the statement that for every pot there exists a lid, the statement that for every lid there exists a pot?
  4. How can you explain that in everyday understanding, the two statements are considered to mean the same thing?


Sketch (as many as possible) essentially different configurations of five lines in the plane, which intersect all together in four intersection points.


For , let

Compute


For every , let

Compute


We consider the value table

  1. Compute .
  2. Compute .
  3. Compute .
  4. Compute .


Prove, by induction, the following formula.


Prove, by induction, the following formula.


Prove the formula

without induction, by considering the following table


The official qualification for the written exam is obtained by reaching at least marks in the exercises altogether. However, Professor Knopfloch says that a mark more or less will not be decisive. Show, by a suitable induction, that one gets the qualification for the written exam with any number of marks.


In the following argumentation, we prove by induction that all horses have the same color. "Let denote the statement, that any horses have the same color. Base case: If only one horse is there, then this has a certain color and the statement is true. For the induction step, suppose that in each collection of horses, they have the same color. Let's now consider a set of horses. If we take out one of them, then by induction hypothesis, all the remaining horses have the same color. If we take out another horse, then again the remaining horses have the same color. Therefore, also all horses have the same color“. Analyze this argumentation.


A natural number is called special if it fulfills a specific explicit property. is special, as the neutral element of the addition, and is special, as the neutral element of the multiplication. is the first prime number, is the smallest odd prime number, is the first true square number, is the number of fingers of one hand, is the smallest number composite of different prime numbers, is the number of dwarfs in the fairy tale, etc., so these numbers are all special. Does there exist a number which is not special? Does there exist a smallest number which is not special?


Show that (with being the only exception) the relation

holds.


Show, by induction, that for every , the number

is a multiple of .


Prove, by induction, that the following inequality holds


Prove, by induction, that the formula

holds for all .


Prove, by induction, that the sum of consecutive odd numbers (starting from ) is always a square number.


The cities are connected by roads, and there is exactly one road between each couple of cities. Due to construction works, at the moment all roads are drivable only in one direction. Show that nevertheless, there exists one city from which you can reach all the others.


Rabbits are born in the middle of the month, the times of gestation is one month, and they reach sexual maturity at the age of two months. Every litter consists of two rabbits, and they live forever.

We start in month with just one couple, whose age is one month. Let denote the number of couples of rabbits in the -th month, hence , . Prove, by induction, the recursive formula

This sequence is called the sequence of the Fibonacci numbers. How many of the couples are in the -th month able to reproduce?


The sequence of Fibonacci numbers is recursively defined by

Determine the first ten Fibonacci numbers.


Prove, by induction, the Simpson formula (or Simpson identity) for the Fibonacci numbers . It says ()


Once in a while, there will be exercises dealing with programs. They are about to describe an algorithm with pseudocode. The pseudocode has to be precise, logical and widely understandable, do not use parts of any programming language. What the computer (the machine) is able to do, will depend on the exercise and is described explicitly.

Write a computer-program (in pseudocode) which decides for a given natural number whether is a prime number or not.

  • The computer has as many memory units as needed, which can contain natural numbers.
  • It can empty memory units.
  • It can increase the content of a memory unit by .
  • It can add the content of two memory units and write the result into another memory unit.
  • It can compare the content of memory units and can, depending on the outcome, switch to a certain program line.
  • It can print contents of memory units and it can print given texts.
  • There is a stop command.

The initial configuration is

with . The program is supposed to print " is a prime number“ or " is not a prime number“ and then stop.


Write a computer-program (in pseudocode) that prints the sequence of the Fibonacci numbers (so ).

  • The computer has as many memory units as needed, which can contain natural numbers.
  • It can write the content of a memory unit into another memory unit.
  • It can add the content of two memory units and write the result into another memory unit.
  • It can print contents of memory units and it can print given texts.
  • There is a stop command.

The initial configuration is

The program runs without stopping and prints "the -th Fibonacci number is .“


Let denote a statement (or rather a form of a statement) in which one can insert natural numbers. Discuss the difference between the two statements

What is the mathematical relevance of the two statements?


By Collatz recursion, we understand the following procedure to construct from a given natural number a new number.

If is even, then take the half of .

If is odd, then multiply with and add .

The Collatz sequence for the initial value is the sequence of numbers arising by applying the Collatz recursion to recursively.

Compute the Collatz sequence for the initial value in your head, until the value is reached.


The Collatz problem is the question whether, starting with any number, the corresponding Collatz sequence ends at . This is an open problem of mathematics.



Hand-in-exercises

Exercise (2 marks)

We understand the statement "Hedgehogs have spikes“ as "Every hedgehog has at least one spike“. Which of the following statements are equivalent with the negation of this statement.

  1. There does not exist a hedgehog which does not have a spike.
  2. All hedgehogs do not have spikes.
  3. There exists a hedgehog, which does not have a spike.
  4. There exists a spike which does not belong to a hedgehog.
  5. There exists a hedgehog without spikes.
  6. There exist many hedgehogs without spikes.
  7. There exists at least one hedgehog which has at least one spike.
  8. There exists at least one hedgehog which has at most one spike.
  9. Not every hedgehog has at least one spike.
  10. Porcupines also have spikes.


Exercise (6 marks)

The expression means that is a friend of . We consider the sentence "All friends of Paula () are also friends of Susanna ().“ Answer, for each of the following formulations, what they mean in usual language, whether they are true, and whether they express the mentioned sentence (the quantifiers are with respect to the set of all people).


Exercise (3 marks)

Fix . Show, by induction, that the following identity holds.


Exercise (4 marks)

An -chocolate is a rectangular grid, which is divided by longitudinal grooves and by transverse grooves into smaller bite-sized rectangles. A dividing step of a chocolate is the complete severing of a chocolate, along a longitudinal or a transverse groove. A complete breakdown of a chocolate is a consequence of division steps (each one applied to a previously obtained intermediate chocolate), whose final product consists of all the small bite-sized pieces, more handy to be eaten. Show, by induction, that each breakdown of an -chocolate consists of exactly division steps.


Exercise (2 marks)

Prove, by induction, that the sequence of the Fibonacci numbers satisfies the pattern

odd-odd-even.


Exercise (2 (1+1) marks)

  1. Determine the members of the Collatz sequence for the initial value .
  2. Compute .


Exercise (5 marks)

Write a computer-program (in pseudocode) which, for a given natural number , computes the corresponding Collatz sequence, and stops, when it reaches .

  • The computer has as many memory units as needed, which can contain natural numbers.
  • It can empty memory units.
  • It can increase the content of a memory unit by .
  • It can write the content of a memory unit into another memory unit.
  • It can add the content of two memory units and write the result into another memory unit.
  • It can compare the content of memory units and can, depending on the outcome, switch to a certain program line.
  • It can print contents of memory units and it can print given texts.
  • There is a stop command.

The initial configuration is

The program is supposed to print out the Collatz sequence starting with and to stop when is reached.



<< | Mathematics for Applied Sciences (Osnabrück 2023-2024)/Part I | >>
PDF-version of this exercise sheet
Lecture for this exercise sheet (PDF)