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

Exercises

Exercise Create referencenumber

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

Lucy Sonnenschein

Exercise Create referencenumber

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

Exercise Create referencenumber

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.

Exercise Create referencenumber

Formulate the following unary predicates within the natural numbers ${}\mathbb {N} =\{0,1,2,3,\ldots \}$, only using equality, addition, multiplication and logical connectives and quantifiers.

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

Exercise Create referencenumber

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 ${}T$ denote the set of pots and let ${}D$ be the set of lids. Let ${}P$ denote the binary predicate such that (for ${}x\in T$ and ${}y\in D$) ${}P(x,y)$ means that ${}y$ is suitable for ${}x$. 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?

Exercise Create referencenumber

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

Exercise Create referencenumber

For ${}k=1,\ldots ,8$, let

${}a_{k}=2^{k}-5k\,.$

Compute

$\sum _{k=1}^{8}a_{k}.$

Exercise Create referencenumber

For every ${}k\in \mathbb {N}$, let

${}a_{k}={\frac {k}{2k+1}}\,.$

Compute

$\sum _{k=0}^{5}a_{k}.$

Exercise Create referencenumber

We consider the value table

${}i$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}a_{i}$	${}2$	${}5$	${}4$	${}-1$	${}3$	${}5$	${}-2$	${}2$

1. Compute ${}a_{2}+a_{5}$.
2. Compute ${}\sum _{k=3}^{6}a_{k}$.
3. Compute ${}\prod _{i=0}^{3}a_{2i+1}$.
4. Compute ${}\sum _{i=4}^{5}a_{i}^{2}$.

===Exercise Exercise 2.10

change===

Prove, by induction, the following formula.

${}\sum _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}\,.$

Exercise Create referencenumber

Prove, by induction, the following formula.

${}\sum _{i=1}^{n}i^{3}={\left({\frac {n(n+1)}{2}}\right)}^{2}\,.$

Exercise Create referencenumber

Prove the formula

${}\sum _{k=1}^{n}k={\frac {n(n+1)}{2}}\,$

without induction, by considering the following table

${}k$	${}1$	${}2$	${}3$	${}\ldots$	${}n-2$	${}n-1$	${}n$
${}n+1-k$	${}n$	${}n-1$	${}n-2$	${}\ldots$	${}3$	${}2$	${}1$

Exercise Create referencenumber

The official qualification for the written exam is obtained by reaching at least ${}200$ 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.

Exercise Create referencenumber

In the following argumentation, we prove by induction that all horses have the same color. "Let ${}A(n)$ denote the statement, that any ${}n$ 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 ${}n$ horses, they have the same color. Let's now consider a set of ${}n+1$ horses. If we take out one of them, then by induction hypothesis, all the remaining ${}n$ horses have the same color. If we take out another horse, then again the remaining horses have the same color. Therefore, also all ${}n+1$ horses have the same color“. Analyze this argumentation.

Exercise Create referencenumber

A natural number is called special if it fulfills a specific explicit property. ${}0$ is special, as the neutral element of the addition, and ${}1$ is special, as the neutral element of the multiplication. ${}2$ is the first prime number, ${}3$ is the smallest odd prime number, ${}4$ is the first true square number, ${}5$ is the number of fingers of one hand, ${}6$ is the smallest number composite of different prime numbers, ${}7$ 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?

Exercise Create referencenumber

Show that (with ${}n=3$ being the only exception) the relation

${}2^{n}\geq n^{2}\,$

holds.

Exercise * Create referencenumber

Show, by induction, that for every ${}n\in \mathbb {N}$, the number

$6^{n+2}+7^{2n+1}$

is a multiple of ${}43$.

Exercise Create referencenumber

Prove, by induction, that the following inequality holds

${}1\cdot 2^{2}\cdot 3^{3}\cdots n^{n}\leq n^{\frac {n(n+1)}{2}}\,.$

Exercise * Create referencenumber

Prove, by induction, that the formula

${}\sum _{k=1}^{n}(-1)^{k-1}k^{2}=(-1)^{n+1}{\frac {n(n+1)}{2}}\,$

holds for all ${}n\in \mathbb {N} _{+}$.

Exercise * Create referencenumber

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

Exercise Create referencenumber

The cities ${}S_{1},\ldots ,S_{n}$ 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.

Exercise Create referencenumber

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 ${}1$ with just one couple, whose age is one month. Let ${}f_{n}$ denote the number of couples of rabbits in the ${}n$-th month, hence ${}f_{1}=1$, ${}f_{2}=1$. Prove, by induction, the recursive formula

${}f_{n+2}=f_{n+1}+f_{n}\,.$

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

The sequence of Fibonacci numbers ${}f_{n}$ is recursively defined by

$f_{1}:=1\,,f_{2}:=1{\text{ and }}f_{n+2}:=f_{n+1}+f_{n}$

Exercise Create referencenumber

Determine the first ten Fibonacci numbers.MDLD/Fibonacci numbers

Exercise * Create referencenumber

Prove, by induction, the Simpson formula (or Simpson identity) for the Fibonacci numbers ${}f_{n}$. It says (${}n\geq 2$)

${}f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\,.$

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.

Exercise Create referencenumber

Write a computer-program (in pseudocode) which decides for a given natural number ${}n\geq 2$ whether ${}n$ 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 ${}1$.

• 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

$(n,0,0,0,0,0,0,\ldots )$

with ${}n\geq 2$. The program is supposed to print "${}n$ is a prime number“ or "${}n$ is not a prime number“ and then stop.

Exercise Create referencenumber

Write a computer-program (in pseudocode) that prints the sequence of the Fibonacci numbersMDLD/Fibonacci numbers (so ${}f_{1}=1,f_{2}=1,f_{3}=2,f_{4}=3,f_{5}=5,f_{6}=8,f_{7}=13,...$).

• 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

$(1,0,0,0,0,0,0,\ldots ).$

The program runs without stopping and prints "the ${}n$-th Fibonacci number is ${}f_{n}$.“

Exercise Create referencenumber

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

${\left(\forall nA(n)\right)}\rightarrow {\left(\forall nA(n+1)\right)}\,\,{\text{ and }}\,\,\forall n{\left(A(n)\rightarrow A(n+1)\right)}.$

What is the mathematical relevance of the two statements?

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

If ${}k$ is even, then take the half of ${}k$.

If ${}k$ is odd, then multiply ${}k$ with ${}3$ and add ${}1$.

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

Exercise Create referencenumber

Compute the Collatz sequenceMDLD/Collatz sequence for the initial value ${}100$ in your head, until the value ${}1$ is reached.

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

Hand-in-exercises

Exercise (2 marks) Create referencenumber

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) Create referencenumber

The expression ${}F(x,y)$ means that ${}x$ is a friend of ${}y$. We consider the sentence "All friends of Paula (${}P$) are also friends of Susanna (${}S$).“ 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).

1. $\forall x\exists yF(x,y),$

2. $\forall xF(P,x)\rightarrow \forall xF(S,x),$

3. $\forall x\forall y{\left(F(x,y)\rightarrow F(y,x)\right)},$

4. $\forall x\forall y{\left(F(x,y)\rightarrow F(x,y)\right)},$

5. $\exists x\forall yF(x,y),$

6. $\forall x{\left(F(P,x)\rightarrow F(x,S)\right)},$

7. $\forall x{\left(\forall y{\left(F(x,y)\rightarrow \forall zF(x,z)\right)}\right)},$

8. $\forall xF(x,P)\rightarrow \forall xF(x,S),$

9. $\forall x{\left(F(x,P)\rightarrow F(x,S)\right)},$

10. $\forall x{\left(\forall yF(x,y)\rightarrow F(x,x)\right)},$

11. $\forall xF(x,x),$

12. $\exists x\forall y{\left(\neg F(x,y)\right)}.$

Exercise (3 marks) Create referencenumber

Fix ${}m\in \mathbb {N}$. Show, by induction, that the following identity holds.

${}(2m+1)\prod _{i=1}^{m}(2i-1)^{2}=\prod _{k=1}^{m}(4k^{2}-1)\,.$

Exercise (4 marks) Create referencenumber

An ${}n$-chocolate is a rectangular grid, which is divided by ${}a-1$ longitudinal grooves and by ${}b-1$ transverse grooves into ${}n=a\cdot b$ 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 ${}n$-chocolate consists of exactly ${}n-1$ division steps.

Exercise (2 marks) Create referencenumber

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

odd-odd-even.

Exercise (2 (1+1) marks) Create referencenumber

1. Determine the members ${}a_{0},a_{1},a_{2},\ldots ,a_{10}$ of the Collatz sequenceMDLD/Collatz sequence for the initial value ${}a_{0}=152$.
2. Compute ${}\sum _{i=1}^{8}a_{i}$.

Exercise (5 marks) Create referencenumber

Write a computer-program (in pseudocode) which, for a given natural number ${}n\geq 1$, computes the corresponding Collatz sequence,MDLD/Collatz sequence and stops, when it reaches ${}1$.

• 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 ${}1$.

• 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

$(n,0,0,0,0,0,0,\ldots ).$

The program is supposed to print out the Collatz sequence starting with ${}n$ and to stop when ${}1$ is reached.

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