Exercises – Short Day#
Exercise 1: Python Exercise#
Recursive definitions are particularly useful for a computer’s computations. This exercise gives some examples of this.
Question a#
The factorial function is defined in Example 5.1.1 in the textbook. More specifically, a recursive definition is given in Equation (5.1) and a pseudocode description in the beginning of the Example (Algorithm 8). If needed, refresh your memory in particular in regards to the pseudocode. The following Python code is a direct “translation” of the pseudocode from Algorithm 8 in the textbook.
def fac(n):
if n == 1: # This is the base case
return 1
else: # This is the recursive case
return(fac(n-1)*n)
Copy the Python code by clicking on the “copy” icon that you see in the upper-right corner when hovering over the gray code box above. Paste the code into command console Python. Now run the command fac(5) to try it out. Does this give you a result you would expect? What What about fac(500) and fac(1000)?
Trouble shooting
If of some reason the prompt in the command console shows ... after you have pasted the Python code, then press the Enter key until the prompt changes to >>>. You should now be able to type the command fac(5).
Answer
fac(5) and fac(500) give the right outcomes.
fac(1000) usually giveS an error message because the function calls itself too many times. Mathematically there is nothing wrong here, but all computer systems have their limits. Here we realise that there is a limit to how many times a function is allowed to call itself recursively in Python. By default, Python has a so-called recursion depth of 1000.
Question b#
To further test recursive definitions we can write the following Python code to define a function \(h: \mathbb{N} \to \mathbb{R}\) recursively:
def h(n):
if n == 1: # This is the base case
return 11
else: # This is the recursive case
return(h(n**2-5*n+7))
Copy the code to command console Python and run the commands h(1), h(2), h(3), and h(4). Check by hand that the output is what it is supposed to be.
Question c#
Now try computing \(h(5)\) by hand. What is the problem? Also run the command h(5) in Python, but remember that you can abort a running Python program by holding the Ctrl key and pressing “c”.
Hint
A similar problem arises with the recursive definition of function \(g\) just before Example 5.1.2 in the textbook.
Answer
If you try to compute \(h(5)\) by hand you will get
We see that in each iteration \(h\) calls itself with a larger input value than before. Hence the recursion never ends.
Exercise 2: Recursions of Depth Two#
Question a#
A sequence of numbers \(c_1,c_2,c_3,\dots\) is defined as follows:
\(c_1=3\), \(c_2=1\) and \(c_{n}=n\cdot c_{n-1}+c_{n-2}\) if \(n \ge 3\).
Compute manually the value of \(c_6\).
Hint
If needed, first read the recursive definition of the Fibonacci numbers in Example 5.1.2 in the textbook.
Hint
The numbers \(c_1\) and \(c_2\) are known. Thus you can compute \(c_3\) via the recursive definition. It gives the formula \(c_3=3c_2+c_1\) for \(n=3\). Afterwards \(c_4\) can be computed, then \(c_5\) and so on.
Answer
\(c_6=811\) (along the way in the computations one will also find that \(c_3=6\), \(c_4=25\) and \(c_5=131\)).
Question b#
Another sequence of numbers \(d_1,d_2,d_3,\dots\) is defined as follows:
\(d_1=1\), \(d_2=2\) and \(d_{n}=d_{n-1}d_{n-2}-n+1\) if \(n \ge 3\).
Check that \(d_6=7\).
Hint
As in Question a it is a good strategy to first compute \(d_3\), then \(d_4\), and so on.
Hint
The recursion gives \(d_3=d_2d_1-3+1\), \(d_4=d_3d_2-4+1\), etc.
Answer
While doing the calculations you might find that \(d_3=0\), \(d_4=-3\), \(d_5=-4\) and finally \(d_6=7\).
Opgave 3: Dot notation#
Given a natural number \(n\) and complex numbers \(a_1,\dots,a_n\). Their sum is denoted by \(a_1+\cdots+a_n\) and sometimes by \(a_1+a_2+\cdots+a_n\). In this exercise some examples that touch upon this topic will be investigated.
Question a#
We define \(a_k=2k\) for \(k=1,2,3,4\). What is \(a_1+\cdots+a_n\) if \(n=4\)? And what if \(n=3\)?
Answer
\(n=4\): \(a_1+a_2+a_3+a_4=2+4+6+8=20\).
\(n=3\): \(a_1+a_2+a_3=2+4+6=12\).
Question b#
Repeat the question, but this time for \(n=2\) and for \(n=1\).
Answer
\(n=2\): \(a_1+a_2=2+4=6\). Meaning, the “dots” should actually just be ignored in the notation \(a_1+\cdots+a_n\) if \(n=2\).
\(n=1\): Now the answer is just \(a_1=2\). Meaning, the notation \(a_1+\cdots+a_n\) for \(n=1\) is a bit misleading since we actually do not have a sum with multiple terms but just the term \(a_1\). This is one reason that many prefer the summation notation with the sum symbol (\(\sum\) notation) instead.
Question c#
A function \(f: \mathbb{N} \to \mathbb{C}\) is given by the expression \(f(k)=k^2-k\). Compute \(f(1)+\cdots + f(n)\) for \(n=1,2,3\) and \(4\).
Answer
\(n=1\): \(f(1)=0\).
\(n=2\): \(f(1)+f(2)=0+2=2\).
\(n=3\): \(f(1)+f(2)+f(3)=2+f(3)=2+6=8\).
\(n=4\): \(f(1)+f(2)+f(3)+f(4)=8+f(4)=8+12=20\).
Exercise 4: Summation Notation#
The summation symbol is defined recursively in Equation (5.5) in the textbook. It can be used with a compact notation form like \(\sum_{x=a}^b f(x)\) or in a full notation form like \(\displaystyle{\sum_{x=a}^b f(x)}.\) In this exercise we investigate this notation, which is called summation notation or sigma notation.
Question a#
Compute \(\sum_{k=1}^4 k^2\).
What is \(\sum_{k=1}^1 k^2\)?
Answer
\(\sum_{k=1}^4 k^2=1^2+2^2+3^2+4^2=30.\)
\(\sum_{k=1}^1 k^2=1^2=1.\)
Question b#
We write \(k!\) for \(k\) factorial in this exercise and use the usual definition of \(0!=1\).
Compute \(\sum_{k=0}^4 1/k!\).
Answer
\(\sum_{k=0}^4 k^2=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}=\frac{1}{1}+\frac{1}{1}+\frac{1}{2}+\frac{1}{6}+\frac{1}{24}=\frac{65}{24}.\)
Note: It can be shown that the sum \(\sum_{k=0}^n 1/k!\) goes towards the number \(\mathrm e\) when \(n\) goes towards infinity.
Exercise 5: Hermite Polynomials#
In this exercise we will define a sequence of polynomials \(\mathrm{He}_0(Z), \mathrm{He}_1(Z), \dots\) with integer-coefficients that are called the Hermite polynomials. These polynomials appear in many different connections such as in signal treatment, propability calculations, and quantum mechanics. The Hermite polynomials can be defined recursively as follows:
\(\mathrm{He}_0(Z)=1\), \(\mathrm{He}_1(Z)=Z\) and \(\mathrm{He}_n(Z)=Z\mathrm{He}_{n-1}(Z)-(n-1)\mathrm{He}_{n-2}(Z)\) if \(n \ge 2\).
What is \(\mathrm{He}_n(Z)\) for \(n=0,1,\dots,4\)?
Answer
\(\mathrm{He}_0(Z)=1\), \(\mathrm{He}_1(Z)=Z\), \(\mathrm{He}_2(Z)=Z^2-1\), \(\mathrm{He}_3(Z)=Z^3-3Z\) and \(\mathrm{He}_4(Z)=Z^4-6Z^2+3\).
Exercise 6: A Recursively Defined Antiderivative#
In Exercise 6 from Week 2’s Short Day the formula \(\mathrm{arctan}'(x)=1/(1+x^2)\) was mentioned. This means that
If \(n\) is a natural number then we might likewise ask whether a similar formula for the following indefinite integral exists:
It turns out that there is a recursive answer to this question.
Question a#
The product rule states that \((f(x)\cdot g(x))'=f(x)' \cdot g(x)+f(x) \cdot g(x)'\). You can find this and other rules for differentiation in Appendix A.2 in the textbook. Justify that
This formula is called integration by parts.
Hint
The function \((f(x)\cdot g(x))'\) has the antiderivative \(f(x) \cdot g(x)\). On the other hand one can rewrite \((f(x)\cdot g(x))'\) using the product rule.
Question b#
Use integration by parts on \(f(x)=x\) and \(g(x)=1/(1+x^2)^n\) in order to realise that
Question c#
Now use the formula
to conclude that
Then solve for \(\int \frac{1}{(1+x^2)^{n+1}}\mathrm dx\) in the last formula and conclude that if \(n \ge 1\), then it applies that
This formula is precisely what we needed! The formula expresses an antiderivative of \(1/(1+x^2)^{n+1}\) as a sum of the function \(\frac{x}{2n(1+x^2)^n}\) and an antiderivative of \(1/(1+x^2)^{n}\). Hence the formula can be used to determine an antiderivative of \(1/(1+x^2)^{n+1}\) in a recursive way.
Question d#
Use the recursion you have found to determine an antiderivative of \(1/(1+x^2)^2\).
Answer