Exercises – Short Day#
Exercise 1: Revision of recursion and summation notation#
We define a sequence of numbers \(c_0,c_1,c_2,\dots\) recursively as follows:
\(c_0=0\), \(c_1=1\), \(c_2=2\), and for \(n \ge 3\) we let \(c_n=c_{n-1}c_{n-2}+c_{n-3}\).
Question a#
What are the values of \(c_3\), \(c_4\) and \(c_5\)?
Answer
\(c_3=c_2c_1+c_0=2\cdot 1+0=2.\)
\(c_4=c_3c_2+c_1=2\cdot 2+1=5.\)
\(c_5=c_4c_3+c_2=5\cdot 2+2=12.\)
Question b#
What is the value of \(\sum_{k=0}^n c_k\) for \(n=0,1,2,3,4,5\)?
Hint
Instead of the summation symbol, dot notation can also be used: \(\sum_{k=0}^n c_k=c_0+\cdots + c_n\).
Answer
\(\displaystyle\sum_{k=0}^0c_k=c_0=0.\)
\(\displaystyle\sum_{k=0}^1c_k=c_0+c_1=1.\)
\(\displaystyle\sum_{k=0}^2c_k=c_0+c_1+c_2=1+2=3.\)
\(\displaystyle\sum_{k=0}^3c_k=c_0+c_1+c_2+c_3=3+c_3=5.\)
\(\displaystyle\sum_{k=0}^4c_k=c_0+c_1+c_2+c_3+c_4=5+c_4=10.\)
\(\displaystyle\sum_{k=0}^5c_k=c_0+c_1+c_2+c_3+c_4+c_5=10+c_5=22.\)
Exercise 2: The sum of odd numbers and induction#
Question a#
For \(n=1,2,3,4\), calculate the sum of the first \(n\) odd natural numbers. In other words, calculate the value of \(\sum_{k=1}^n (2k-1)\) for \(n \in \{1,2,3,4\}\). Do you see a pattern in these values?
Now, find (or guess) a simple expression for \(\sum_{k=1}^n (2k-1)\) that produces the right answer for \(n \in \{1,2,3,4\}\), and check that your guess also produces the right value of \(\sum_{k=1}^n (2k-1)\) for \(n=5\).
Hint
The values are all perfect squares.
Answer
\(\displaystyle\sum_{k=1}^1 (2k-1) = 1\), \(\displaystyle\sum_{k=1}^2 (2k-1) = 4\), \(\displaystyle\sum_{k=1}^3 (2k-1) = 9\) and \(\displaystyle\sum_{k=1}^4 (2k-1) = 16\).
Based on this, it is reasonable to guess that \(\sum_{k=1}^n (2k-1)=n^2\) holds for all natural numbers \(n\). For \(n=5\), this guess fits as well: \(5^2=25\) and \(1+3+5+7+9=25\).
Question b#
Let \(P(n)\) be the logical proposition that \(\sum_{k=1}^n (2k-1)\) equals the short expression you provided in Question a. Now the goal is to show that \(P(n)\) is true for all natural numbers \(n\) (that is, for all \(n \in \mathbb{N}=\mathbb{Z}_{\ge 1}\)).
Show that the base case of the induction holds.
Hint
The base case is the proposition \(P(1)\). In other words, to show that the base case holds, you must show that \(P(1)\) is true.
Answer
\(P(1)\) is the proposition that \(\sum_{k=1}^1 (2k-1) = 1^2\), which we showed to hold true in Question a. In fact, from Question a we know that \(P(n)\) holds for \(n \in \{1,2,3,4,5\}\), but for the base case of the induction, checking the case where \(n=1\) is sufficient.
Question c#
Now carry out the induction step, and then use the induction principle to conclude that \(P(n)\) is true for all natural numbers \(n\).
Hint
In the induction step you must show that, for an arbitrary integer \(n \ge 2\), the implication \(P(n-1) \Rightarrow P(n)\) is true. In other words, for the induction step you may assume that \(P(n-1)\) is true (this is what we call the induction hypothesis), and then you must show that under this assumption, \(P(n)\) is also true.
Hint
In the induction step, the recursive definition of the summation symbol as given in Equation (3.5) in the textbook will be useful.
Exercise 3: A geometric series#
A geometric sequence is a sequence of numbers in which each number equals the previous number times a fixed factor. A geometric series is the sum of such a geometric sequence. Let us study such geometric series in this exercise and the next.
Let \(r \in \mathbb{C} \setminus \{1\}\) be a complex number and \(n\) a natural number. We wish to prove the following identity:
Question a#
Why can \(r\) not be equal to \(1\) in this identity?
Answer
If \(r=1\), then the denominator in the fraction \(\frac{r^{n+1}-1}{r-1}\) equals zero. Thus, the fraction is not defined for \(r=1\).
Question b#
Check that the identity holds for \(n=1\).
Hint
If we consider the expression \(r^2-1\) as a polynomial in the variable \(r\), then it has the two roots \(1\) and \(-1\). Now, use Lemma 5.6.2 in the textbook to write \(r^2-1\) as a product of two linear (first-degree) polynomials.
Question c#
Show that the identity \(\displaystyle 1+r+\cdots + r^n= \frac{r^{n+1}-1}{r-1}\) holds for all natural numbers \(n\).
Hint
Use induction on \(n\). Note that the base case has already been handled in Question b.
Hint
For the induction step, the induction hypothesis is that \(1+r+\cdots + r^{n-1}= \frac{r^{n}-1}{r-1}\). Now use the fact that \(1+r+\cdots + r^{n}=(1+r+\cdots + r^{n-1})+r^n\), and then apply the induction hypothesis.
Exercise 4: A bouncing ball as a geometric series#
Question a#
A bouncing ball is released from a height of two metres above the floor. After hitting the floor for the first time, it bounces back up one metre; after the second time, half a metre; after the third, a quarter of a metre; and so on. In other words, the falling distance is halved for each subsequent drop. Let \(n\) be a natural number. Provide an expression that gives the total distance the ball has travelled when it hits the floor the \(n\)th time.
Hint
The first time the ball hits the floor, it has travelled a total distance of two metres (because it was dropped from an initial height of two metres). The second time, the ball bounces one metre back up and then falls one metre back down again - in total the ball has now travelled \(2+2\cdot 1=4\) metres. The third time, it bounces back up half a metre before falling that half a metre back down again, so in total \(2+2\cdot (1+\frac12)\) metres. Similarly, the fourth time we find the total travel distance to be \(2+2\cdot (1+\frac12+\frac14)\) metres. Can you see a pattern, and can you express it using the Sigma summation symbol?
Answer
If \(n=1\), the answer is \(2\) metres. For \(n \ge 2\), the answer is \(2+2\cdot \sum_{j=0}^{n-2} \frac{1}{2^j}\).
Question b#
What total distance does the bouncing ball travel before it finally comes to rest on the floor?
Hint
By choosing \(r\) and \(n\) suitably, you can simplify the expression using the identity proved in Exercise 3:
What do you get as \(n\) approaches infinity?
Answer
\(6\) metres.
Exercise 5: An inequality#
A sequence of real numbers \(a_1,a_2,\dots\) is defined recursively as follows:
\(a_1=0\), and \(a_n=\sqrt{2+a_{n-1}}\) if \(n \ge 2\).
Question a#
Calculate \(a_1\), \(a_2\), \(a_3\) and \(a_4\).
Answer
\(a_1=0\), \(a_2=\sqrt{2}\), \(a_3=\sqrt{2+\sqrt{2}}\) and \(a_4=\sqrt{2+\sqrt{2+\sqrt{2}}}\).
Or, numerically, to many decimal places:
\(a_1=0.00000000000000000000000000000\).
\(a_2=1.41421356237309504880168872421\).
\(a_3=1.84775906502257351225636637879\).
\(a_4=1.96157056080646089825236447227\).
Question b#
We now claim that \(a_n<2\) holds for all natural numbers \(n\). Prove this using induction on \(n\).
Hint
For the induction step you may use the fact that the square-root function \(f: \mathbb{R}_{\ge 0} \to \mathbb{R}\) given by \(x\mapsto \sqrt{x}\) is strictly increasing.
Have you finished all the exercises?#
If it went too quickly and you are eager for more, then click here for some challenging optional extra exercises.