Tutorial
Tutorial#
Similarly to the previous chapter, we will use a computer to gain numerical evidence for a problem.
Problem
The Fibonacci numbers are defined by the following sequence:
\[\begin{split}
\left\{\begin{array}{l}
a_0 = 0,\\
a_1 = 1,\\
a_n = a_{n - 1} + a_{n - 2}, n \geq 2\end{array}\right.
\end{split}\]
Verify that the following identity holds for \(n\leq 500\):
\[
\sum_{i=0}^n a_i = a_{n + 2} - 1
\]
We will start by defining a function for \(a(n)\):
import functools
@functools.lru_cache()
def get_fibonacci(n):
"""
A function to give the nth Fibonacci number using the recursive
definition.
Note that this also uses a cache.
Parameters
----------
n: int
The index of the Fibonacci number
Returns
-------
int
The nth Fibonacci number
"""
if n == 0:
return 0
if n == 1:
return 1
return get_fibonacci(n - 1) + get_fibonacci(n - 2)
Attention
We are using caching in that function definition with lru_cache. This is not
necessary but makes the code more efficient. We spoke about caching in
What is caching.
We will print the first 10 numbers to ensure everything is working correctly:
for n in range(10):
print(get_fibonacci(n))
0
1
1
2
3
5
8
13
21
34
Now we will write a function that returns a boolean: True if the equation
holds for a given value of \(n\), False otherwise.
def check_theorem(n):
"""
A function that generate the lhs and rhs of the
following relationship:
\sum_{i=0}^n a_i = a_{n + 2} - 1
Where `a_i` is the i-th Fibonacci number.
It checks if the relationship holds.
Parameters
----------
n: int
The index n for which the theorem is to be verified.
Returns
-------
bool
Whether or not the theorem holds for a given n.
"""
sum_of_fibonacci = sum(get_fibonacci(i) for i in range(n + 1))
return sum_of_fibonacci == get_fibonacci(n + 2) - 1
We can then generate checks for \(n\leq 500\):
checks = [check_theorem(n) for n in range(501)]
checks
[True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True,
True]
Confirm that all the booleans in check are True:
all(checks)
True
Attention
Similarly to and and or (see How to combine boolean variables), all
is an operator that takes an iterable of booleans and returns if they are all
True. Another similar operator is any.